题目链接：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.
这道题的要求是找到数组中的主要元素（指的是出现次数超过数组大小一半的元素），假设数组非空并且肯定存在主要元素。
可以暴力解决，就是统计每个数字出现的次数，返回最大值即可。时间复杂度O(n^2)。
-
Hash表
建Hash表，统计每个数字出现的次数，返回最大的或者出现次数超过数组大小一半的。
时间复杂度：O(n)
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution
{
public:
int majorityElement(vector<int> &num)
{
unordered_map<int, int> cnt;
for(int i = 0; i < num.size(); ++ i)
++ cnt[num[i]];
for(auto it = cnt.begin(); it != cnt.end(); ++ it)
if(it -> second > num.size() / 2)
return it -> first;
return 0;
}
};
-
Sort排序
先排序，然后返回数组中的⌊ n/2 ⌋位置的元素。
由于必有主要元素，因此⌊ n/2 ⌋位置的元素就是主要元素。
时间复杂度：O(nlogn)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
class Solution {
public:
int majorityElement(vector<int> &num)
{
sort(num.begin(), num.end());
return num[num.size() / 2];
}
};
-
分治
将数组拆分成左右2个子区间，分别统计每个区间的主要元素a和b。
- 如果a等于b，那么a（或者b）就是全局主要元素；
- 否则，分别统计a和b出现的次数，出现多的就是主要元素。
至于求子区间的主要元素，可以递归进行处理。
时间复杂度：O(nlogn)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int majorityElement(vector<int> &num)
{
return majorityElement(num, 0, num.size() - 1);
}
private:
int majorityElement(vector<int> &num, int l, int r)
{
if(l == r)
return num[l];
int m = (l + r) / 2;
int a = majorityElement(num, l, m);
int b = majorityElement(num, m + 1, r);
if(a == b)
return a;
int cnt_a = 0, cnt_b = 0;
for(int i = l; i <= r; ++ i)
{
cnt_a += num[i] == a ? 1 : 0;
cnt_b += num[i] == b ? 1 : 0;
}
return cnt_a > cnt_b ? a : b;
}
};
-
Moore投票
用cur维护当前元素，cnt维护当前元素的数量。每次读取元素：
- 如果cnt等于0，说明没有当前元素，那么cur赋值成刚读取的元素，同时cnt置1；
- 否则，如果刚读取的元素与cur相同，cnt加1；如果不同，cnt减1。
这样，最后剩下的cnt就是数量多于数组大小一半的主要元素。
时间复杂度：O(n)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int majorityElement(vector<int> &num)
{
int cur = 0, cnt = 0;
for(int i = 0; i < num.size(); ++ i)
{
if(cnt == 0)
{
cur = num[i];
++ cnt;
}
else
cur == num[i] ? ++ cnt : -- cnt;
}
return cur;
}
};
-
位操作
由于必有某一元素数量超过数组大小一半，因此该元素的每一位上的数字也是所有元素中对应位上最多的，因此只需统计每位上0和1出现的次数即可。
- 如果某位上1出现次数大于0，那么结果该位为1；
- 否则，结果该位为0。（不会出现相等情况）
时间复杂度：O(n)
空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int majorityElement(vector<int> &num)
{
int res = 0;
for(int i = 0; i < 32; ++ i)
{
int cnt[2] = {0, 0};
for(int j = 0; j < num.size(); ++ j)
++ cnt[(num[j] >> i) & 1];
if(cnt[0] < cnt[1])
res |= 1 << i;
}
return res;
}
};