面试经典150道之多数元素

多数元素

记一个方法

Boyer-Moore 投票算法

思路

Boyer-Moore 投票算法是一种在线性时间和常数空间内找到多数元素的高效算法。其基本思想是通过消除不同的元素来找到可能的多数元素。

算法步骤

1. ​​初始化​​：选择数组的第一个元素作为候选多数元素，并设置计数器为1。

2. ​​遍历数组​​：

   • 如果当前元素与候选多数元素相同，则增加计数器。

   • 如果不同，则减少计数器。

   • 如果计数器变为0，则更换候选多数元素为当前元素，并重置计数器为1。

3. ​​结果​​：遍历结束后，候选多数元素即为所求的多数元素。

为什么有效？

由于多数元素的数量超过数组的一半，即使其他元素与多数元素相互抵消，最终剩下的候选元素一定是多数元素。

代码部分：

class Solution {public int majorityElement(int[] nums) {int count = 0;Integer candidate = null;for (int num : nums) {if (count == 0) {candidate = num;}count += (num == candidate) ? 1 : -1;}return candidate;}
}

我用的是哈希表方法，也就是用一个map存储数字和它出现的次数