题目
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.
Example 1:
1
2
| Input: [3,2,3]
Output: 3
|
Example 2:
1
2
| Input: [2,2,1,1,1,2,2]
Output: 2
|
解题报告
哈希表
- 对每一个元素计数，找到大于 n/2 的元素返回即可
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
int majorityElement(vector<int>& numbers) {
unordered_map<int,int> map_;
for (int num:numbers) {
if (++map_[num] > numbers.size() / 2)
return num;
}
return 0;
}
};
|
排序
- 因为满足需求的个数是至少 n / 2， 因此只需要找到排序后处于一半位置的元素就是答案。
1
2
3
4
5
6
7
| class Solution {
public:
int majorityElement(vector<int>& numbers) {
nth_element(numbers.begin(), numbers.begin() + numbers.size() / 2, numbers.end());
return numbers[numbers.size()/2];
}
};
|
Divide and Conquer
- 递归的找两部分的 majority，最后合并结果，递归出口就是单个元素
algorithm 中有个 count 函数，类似于 find，主要是使用一对迭代器和一个值作为参数，返回值出现的次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int majorityElement(vector<int>& numbers) {
function<int(vector<int>, int ,int )> majorityElementHelper = [&](vector<int> element, int l, int r){
if (l == r) return element[l];
int m = l + (r-l)/2;
int lm = majorityElementHelper(elements, l, m);
int rm = majorityElementHelper(elements, m+1, r);
if (lm == rm) return lm;
return count(nums.begin() + l, nums.begin() + r + 1, lm) > count(nums.begin() + l, nums.begin() + r + 1, rm) ? lm : rm;
};
return majorityElementHelper(numbers,0, numbers.size() - 1);
}
};
|
Moore Voting Algorithm
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
int majorityElement(vector<int>&numbers) {
int count = 0, majority;
for (auto num:numbers) {
if (!count) {
majority = num;
}
count += (num == majority) 1 : -1;
}
return majority;
}
};
|
位操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
int majorityElement(vector<int>&numbers) {
int majority = 0;
for (unsigned int i = 0, mask = 1; i < 32; i++, mask <<= 1) {
int bits = 0;
for (int num : numbers) {
if (num & mask) {
bits++;
}
}
if (bits > numbers.size() / 2) {
majority |= mask;
}
}
return majority;
}
};
|
