LeetCode169 Majority Element

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

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;
}
};
分享到 评论