Leetcode169. 多数元素

题目描述

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 $ \lfloor n/2 \rfloor$的元素。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

1
2
输入:[3,2,3]
输出:3

示例 2:

1
2
输入:[2,2,1,1,1,2,2]
输出:2

进阶:

  • 尝试设计时间复杂度为 O(n)O(n)、空间复杂度为$ O(1) $的算法解决此问题。

解题思路

这道题最简单的方法就是哈希法。也就是同一个哈希表去存储每一个元素以及出现的次数,然后返回出现次数大于$ \lfloor n/2 \rfloor$的元素。

这个方法简单易懂,但是时间复杂度为O(n)O(n),空间复杂度也为O(n)O(n),不符合要求。

如果要把空间复杂度优化到O(1)O(1),我们就需要采用非常有名的**$Boyer-Moore $投票算法。**

摩尔投票法充分利用了题目中的一直条件——数组中一定存在出现次数 大于 $ \lfloor n/2 \rfloor的元素。那么如果把多数元素记为的元素。那么如果把多数元素记为+1,其他元素记为,其他元素记为-1,那么他们加起来的和肯定大于0。相反,如果把多数元素记为,那么他们加起来的和肯定大于0 。相反,如果把多数元素记为-1,其他元素记为,其他元素记为+1$,那么他们加起来的和肯定小于0。

具体的做法如下:

  • 我们维护一个候选数flagNum和计数器ret。初始时,flagNum可以为任意数,ret为0;
  • 遍历数组nums中的所有元素。首先判断一下计数器ret的状态,如果ret的值变为了0,说明当前的flagNum不是多数元素,用nums[i]去更新flagNum的值。然后,再依据以下规则,更新ret的值:
    • 如果nums[i]flagNum相等,那么ret的值增加1;
    • 如果nums[i]flagNum不等,那么ret的值减少1。
  • 遍历结束后,flagNum即为所求的元素。

时间复杂度:O(n)O(n)

空间复杂度:O(1)O(1)

根据摩尔投票法写出的示例代码如下。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int majorityElement(vector<int>& nums)
{
int ret=0;
int flagNum;
for(int i=0;i<nums.size();++i)
{
if(ret==0)
{
flagNum=nums[i];
}
if(nums[i]!=flagNum)
{
ret--;
}
else{
ret++;
}
}
return flagNum;
}