27
07/2015
[LeetCode] Majority Element II
Majority Element II
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
解题思路：
此前做了一道题目，返回主要元素，其中主要元素的定义是出现次数大于n/2的元素。当初投票法非常不错。类似的，这道题也可以用投票法，但是稍微复杂一下。注意到，对于一个数组来说，大于n/3的元素最多有2个。于是可以用两个变量来记录出现的候选主要元素。
设候选主要元素为can1，can2，其票数分别是count1，count2（初始化均为0）。逐个扫描nums内的元素nums[i]，分情况讨论。
1、假设还未统计任何数，即count1=0&&count2=0，则can1=nums[i]，count1=1
2、can1和can2其中一个没有初始化（设can2，即count2=0），且nums[i]!=can1，那么can2=nums[i]，count2=1。对称另一种情况容易知道。
3、假设can1和can2两个都初始化了（count1!=0并且count2!=0），但是can1!=nums[i]并且can2!=nums[i]。那么count1和count2均减1
4、若count1!=0并且can1==nums[i]，那么count1++。同样，若count2!=0并且can2==nums[i]，那么count2++。
最后，验证can1和can2的出现次数即可。
下面是代码：
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> result;
int len = nums.size();
int can1=0, count1 = 0, can2 = 0, count2 = 0;
for(int i=0; i<len; i++){
if(count1 == 0 && count2 == 0){
can1 = nums[i];
count1=1;
}else if(count1!=0 && count2!=0 && can1!=nums[i] && can2!=nums[i]){
count1--;
count2--;
}else if(can1==nums[i] && count1!=0){
count1++;
}else if(can2==nums[i] && count2!=0){
count2++;
}else if(count1==0&&count2!=0&&can2!=nums[i]){
can1 = nums[i];
count1++;
}else if(count2==0&&count1!=0&&can1!=nums[i]){
can2 = nums[i];
count2++;
}
}
//这两个只是候选的
if(count1!=0){
count1 = 0;
for(int i=0; i<len; i++){
if(can1==nums[i]){
count1++;
}
}
if(count1>len/3){
result.push_back(can1);
}
}
if(count2!=0){
count2 = 0;
for(int i=0; i<len; i++){
if(can2==nums[i]){
count2++;
}
}
if(count2>len/3){
result.push_back(can2);
}
}
return result;
}
};转载请注明：康瑞部落 » [LeetCode] Majority Element II
0 条评论