C ++中的多数元素II
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int first = 0;
int second = 1;
int cnt1 = 0;
int cnt2 = 0;
int n = nums.size();
for(int i = 0; i < n; i++){
int x = nums[i];
if(x == first){
cnt1++;
}
else if(x == second){
cnt2++;
}
else if(cnt1 == 0){
first = x;
cnt1 = 1;
}
else if(cnt2 == 0){
second = x;
cnt2 = 1;
} else {
cnt1--;
cnt2--;
}
}
cnt1 = 0;
cnt2 = 0;
for(int i = 0; i < n; i++){
if(nums[i] == first)cnt1++;
else if(nums[i] == second)cnt2++;
}
vector <int> ret;
if(cnt1 > n / 3)ret.push_back(first);
if(cnt2 > n / 3)ret.push_back(second);
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1, 1, 1, 3, 3, 2, 2, 2};
print_vector(ob.majorityElement(v));
}输入值
[1,1,1,3,3,2,2,2]
输出结果
[2, 1, ]