/**
* @param {number[]} nums
* @return {number[]}
*/
var majorityElement = function(nums) {
var ret = [];
var len = nums.length;
var threshold = len/
3;
if(len===
0||len==
1){
return nums;
}
var candidate0 = nums[
0];
var candidate1 = Infinity;
var count0 =
1;
var count1 =
0;
for(
var i=
1;i<len;i++){
var tmp = nums[i];
if(tmp == candidate0){
count0++;
}
else if(tmp == candidate1){
count1++;
}
else{
if(count1 ===
0){
candidate1 = nums[i];
count1++;
}
else if(count0 ===
0){
candidate0 = nums[i];
count0++;
}
else{
count0--;
count1--;
}
}
}
count0 =
0;
count1 =
0;
for(i=
0;i<len;i++){
if(nums[i]==candidate0){
count0++;
}
if(nums[i]==candidate1){
count1++;
}
}
if(count0>threshold){
ret.push(candidate0);
}
if(count1>threshold&&candidate1!=candidate0){
ret.push(candidate1);
}
return ret;
};
这道题的难点在于，1、要求 O(1) 的空间复杂度；2、并不保证Majority Element一定存在。
主体的思路和Majority Element是一样的，首先要从数组中找出备选众数。然后进行第二轮查找，确定备选众数能不能真正达到众数的标准。如果能，才能添加到将要返回的数组中。
转载请注明原文地址: https://ju.6miu.com/read-1307989.html
