LeetCode169 Majority Element


描述

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

样例

1
2
3
4
5
Input:
[1, 2, 2, 2]

Output:
2

思路

找出数组中出现次数大于$⌊ n/2 ⌋$次的元素。

一个直观的想法是用$map$记录每个数字出现的次数然后再比较是否大于指定的次数即可。当然,分治也可以做,每次划分成子区间去找,合并的时候看那个出现的次数更多。这两个做法复杂度都是$\mathcal{O}(nlogn)$的。

其实也有线性复杂度的做法。先讲一下位运算的做法,出现次数大于$n/2$次的元素,显然其对应的二进制位出现的次数肯定也大于$n/2$次,所以枚举二进制位然后判断一下次数即可。

然后再介绍一个神奇的算法Moore Voting Algorithm,具体可以参阅A Linear Time Majority Vote Algorithm
主要思想是将两两不同的数相互抵消,剩下没有消掉的肯定是次数超过一半的数。

代码

哈希: $\mathcal{O}(nlogn)$

1
2
3
4
5
6
7
8
class Solution {
public:
int majorityElement(vector<int>& nums) {
int times = nums.size() / 2;
map<int, int> hashTable;
for (int& x: nums) if (++hashTable[x] > times) return x;
}
};

分治:$\mathcal{O}(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int majorityElement(vector<int>& nums) {
return find(nums, 0, nums.size()-1);
}
int find(vector<int>& nums, int l, int r) {
if (l == r) return nums[l];
int m = (l + r) / 2;
int lans = find(nums, l, m), rans = find(nums, m+1, r);
int lcnt = 0, rcnt = 0;
for (int i = l; i <= r; ++i) {
if (nums[i] == lans) lcnt++;
if (nums[i] == rans) rcnt++;
}
return lcnt > rcnt ? lans : rans;
}
};

位运算:$\mathcal{O}(n)$

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int majorityElement(vector<int>& nums) {
int ans = 0, mask = 1, times = nums.size() / 2;
for (int i = 0; i < 32; ++i, mask <<= 1) { // 枚举二进制位
int bitCount = 0;
for (int& x: nums) if (x & mask) bitCount++;
if (bitCount > times) ans |= mask;
}
return ans;
}
};

Moore Voting Algorithm:$\mathcal{O}(n)$

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int majorityElement(vector<int>& nums) {
int ans = 0, cnt = 0;
for (int& x: nums) {
if (!cnt) cnt++, ans = x; // 若没有候选答案,则把当前这个数作为候选答案
else ans == x ? cnt++ : cnt--; // 比较当前的数和候选答案是否相等,不相等则消掉
}
return ans;
}
};