引子
该算法用于寻找数组中出现最多次元素的问题。
算法描述
- 初始化两个变量出现最多次元素的值val和这个元素出现的次数time。
- 遍历数组：
- 若time为0，则将遍历到的当前元素赋值给val。
- 若数组中当前元素与val相同，则让time自增，否则让time自减。
- (可选)检查。
C++实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int BM(vector<int>& arr) {
int val = 0, time = 0;
for(int i : arr) {
if(time == 0) {
val = i;
time = 1;
} else if(i == val) {
++time;
} else {
--time;
}
}
return val;
}
|
该算法的直观理解是这样的，一些人在为一个政治问题投票，如果投票最多的选项是A，那么投其他选项的人都是反对A的人。
实战
Leetcode169. Majority Element题解为：
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) {
int elem = 0, times = 0;
for(int i : nums) {
if(times == 0) {
elem = i;
++times;
} else if(i == elem) {
++times;
} else {
--times;
}
}
return elem;
}
};
|
Leetcode229. Majority Element II题解为：
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
29
30
31
32
33
34
35
36
37
38
| class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;
for (auto num : nums) {
if (candidate1 == num) count1++;
else if (candidate2 == num) count2++;
else if (count1 == 0) {
candidate1 = num;
count1 = 1;
}
else if (count2 == 0) {
candidate2 = num;
count2 = 1;
}
else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int num : nums) {
if (num == candidate1) count1++;
else if (num == candidate2) count2++;
}
vector<int> ans;
if (count1 > nums.size() / 3) ans.push_back(candidate1);
if (count2 > nums.size() / 3) ans.push_back(candidate2);
return ans;
}
};
|
