Majority Element
遍历一次，保存一个长度为k - 1的数组：
如果数组中包括这个数，则该数count + 1
如果数组中有空位，则放入概该，count置为1
如果数组中有数字count为0，则替换该数，count置为1
所有数字count减1
最后数组中剩下的数，就是candidate，每个统计一下就可以了
这个方法可以解决任意1/k的majority number
Majority Element
经典的投票算法。
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;
}
}
Majority Element II
Moore's Voting Algorithm.
遍历一次，保存一个长度为k - 1的数组：
- 如果数组中包括这个数，则该数count + 1
- 如果数组中有空位，则放入该数，count置为1
- 如果数组中有数字count为0，则替换该数，count置为1
- 所有数字count减1
没有想到这一步, 最后要再扫一遍数组. 最后数组中剩下的数，就是candidate; 此时再扫一遍数组，确认每个 candidate 的真正出现次数，并根据时候符合最终要求添加到最终结果里。
在这个算法中，count = 0 并不一定代表这个数不是 majority 应该被“立刻”踢出去。最后扫一遍和count=0并不立刻踢出去有点像find the celebrity.
这个方法可以解决任意n/k的majority number
从思想上说，这种做法有点像蓄水池抽样，又有点像 find the celebrity，都是 streaming data 然后维护固定 size 进行淘汰的机制。
public List<Integer> majorityElement(int[] nums){
int c1=0;int c2=0;int r1=0;int r2=1;
for(int num : nums){
if(num==r1){
c1++;
}
else if(num==r2){
c2++;
}
else if(c1==0){
r1 = num; c1 =1;
}
else if(c2==0){
r2 = num; c2 = 1;
}
else{
c1--;c2--;
}
}
int count1 = 0; int count2=0;
for(int num:nums){
if(r1==num) count1++;
if(r2==num) count2++;
}
//must check, 1, 2, 3 output[2,1]. expect: []
List<Integer> rtn = new ArrayList<Integer>();
if(count1>nums.length/3) rtn.add(r1);
if(count2>nums.length/3) rtn.add(r2);
return rtn;
}
Majority Number III
同样的思路扩展开来的通用解法，不过注意这题说了只会有一个 majority element 所以最后 return 那里有所不同，但是这个算法完全可以找到所有 k - 1 个。
犯错1: Integer ArrayList 要用 arraylist.set(i, num) 而不是 arraylist.get(i) = new Integer (num)
犯错2: 要先加, 再check empty. 在65%的case的时候挂了, 出现了两个198, 191没有被加入. 原因就是先找到了一个空的位置, 将198放入后continue, 忽略了198实际存在在arraylist里.
public int majorityNumber(ArrayList<Integer> nums, int k) {
// write your code
int ans = 0;
List<Integer> e = new ArrayList<Integer>(k);
List<Integer> c = new ArrayList<Integer>(k);
for(int i=0;i<k;i++) {e.add(0);c.add(0);}
for(Integer n : nums){
boolean add = false;
for(int i=0;i<k;i++){
if(e.get(i).equals(n)){
e.set(i, n);
c.set(i, c.get(i)+1);
add = true;
break;
}
}
if(add) continue;
boolean empty = false;
for(int i=0;i<k;i++){
if(e.get(i)==null||c.get(i).equals(0)){
e.set(i, n); c.set(i,1);
empty = true;
break;
}
}
if(empty) continue;
for(int i=0;i<k;i++){
c.set(i, c.get(i)-1);
}
}
for(int i=0;i<k;i++) c.set(i, 0);
for(Integer n : nums){
for(int i=0;i<k;i++)
if(e.get(i).equals(n)) c.set(i, c.get(i)+1);
}
for(int i=0;i<k;i++){
System.out.println(e.get(i) + " " + c.get(i));
if(c.get(i)>nums.size()/k) return e.get(i);
}
return ans;
}
(Google) Majority Element
http://www.1point3acres.com/bbs/thread-191900-1-1.html
之前google面经里有的关于majority element的题，就是一个排序数组有n个值，求所有出现次数等于或者超过n / k的值。 比如[1 1 2 2 2 2 3 4 5 5 5 5] k = 3 return [2,5]