遍历一次，保存一个长度为k - 1的数组：
如果数组中有数字count为0，则替换该数，count置为1
最后数组中剩下的数，就是candidate，每个统计一下就可以了
这个方法可以解决任意1/k的majority number
经典的投票算法。
public class Solution {
public int majorityElement(int[] num) {
int major=num[0], count = 1;
for(int i=1; i<num.length;i++){
if(count==0){
count++;
major=num[i];
}else if(major==num[i]){
count++;
}else count--;
}
return major;
}
}
Moore's Voting Algorithm.
遍历一次，保存一个长度为k - 1的数组： 1. 如果数组中包括这个数，则该数count + 1 2. 如果数组中有空位，则放入该数，count置为1 3. 如果数组中有数字count为0，则替换该数，count置为1 4. 所有数字count减1
最后数组中剩下的数，就是candidate; 此时再扫一遍数组，确认每个 candidate 的真正出现次数，并根据时候符合最终要求添加到最终结果里。
在这个算法中，count = 0 并不一定代表这个数不是 majority 应该被“立刻”踢出去。
这个方法可以解决任意n/k的majority number
从思想上说，这种做法有点像蓄水池抽样，又有点像 find the celebrity，都是 streaming data 然后维护固定 size 进行淘汰的机制。
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> list = new ArrayList<>();
if(nums == null || nums.length == 0) return list;
int count1 = 0;
int count2 = 0;
int num1 = 0;
int num2 = 1;
// 1 and 2 should be initialized to be different numbers
for(int i = 0; i < nums.length; i++){
if(nums[i] == num1){
count1++;
} else if(nums[i] == num2) {
count2++;
} else if(count1 == 0){
num1 = nums[i];
count1 = 1;
} else if(count2 == 0){
num2 = nums[i];
count2 = 1;
} else {
count1 --;
count2 --;
}
}
int n = nums.length;
count1 = 0;
count2 = 0;
for(int i = 0; i < nums.length; i++){
if(nums[i] == num1) count1++;
else if(nums[i] == num2) count2++;
}
if(count1 > n / 3) list.add(num1);
if(count2 > n / 3) list.add(num2);
return list;
}
}
同样的思路扩展开来的通用解法，不过注意这题说了只会有一个 majority element 所以最后 return 那里有所不同，但是这个算法完全可以找到所有 k - 1 个。
public int majorityNumber(ArrayList<Integer> nums, int k) {
// write your code
int n = nums.size();
List<Integer> numList = new ArrayList<>();
List<Integer> countList = new ArrayList<>();
if(nums == null || nums.size() == 0) return -1;
for(int i = 0; i < n; i++){
int num = nums.get(i);
if(numList.size() < k - 1 && !numList.contains(num)){
numList.add(num);
countList.add(1);
} else {
int index = numList.indexOf(num);
if(index != -1){
// current number is in candidate list;
countList.set(index, countList.get(index) + 1);
} else {
int zeroIndex = countList.indexOf(0);
if(zeroIndex != -1){
numList.remove(zeroIndex);
countList.remove(zeroIndex);
numList.add(num);
countList.add(1);
} else {
for(int j = 0; j < countList.size(); j++){
countList.set(j, countList.get(j) - 1);
}
}
}
}
}
//List<Integer> rst = new ArrayList<>();
for(int i = 0; i < numList.size(); i++){
int count = 0;
for(int num : nums){
if(num == numList.get(i)) count++;
}
//if(count > n / k) rst.add(numList.get(i));
if(count > n / k) return numList.get(i);
}
return -1;
}
(Google) Majority Element
之前google面经里有的关于majority element的题，就是一个排序数组有n个值，求所有出现次数等于或者超过n / k的值。 比如[1 1 2 2 2 2 3 4 5 5 5 5] k = 3 return [2,5]
解决办法就是依次检查所有可能的出现 majority element 的位置 [n/k,2n/k, .... ,n] ，在每个位置上根据当前元素做 search for range，O(log n)，如此重复最多 k 次即可。