面试题库 › C++ / 后端 › 数组中出现次数超过一半的数字(摩尔投票)

数组中出现次数超过一半的数字(摩尔投票)

难度 ★★☆在 8 场真实面经中被问到 方向:C++ / 后端考点:数组与字符串

哪些公司问过

腾讯3百度2快手1拼多多1网易雷火1

常见岗位:C/C++ 软件开发、后端开发、C++ 后端、Java 后端、iOS

答案要点

  1. 摩尔投票法:O(n) 时间、O(1) 空间
  2. 维护 candidate 和 count:count 为 0 换候选,相同加一,不同减一
  3. 原理:不同元素两两抵消,超过一半的元素一定剩下
  4. 前提是多数元素一定存在;不确定时需再遍历验证候选数次数
  5. 其他方法:哈希表计数 O(n) 空间;排序取中位数 O(n log n)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题