Majority Element，Moore's Voting

遍历一次，保存一个长度为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的数组： 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 Number III

同样的思路扩展开来的通用解法，不过注意这题说了只会有一个 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

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]

解决办法就是依次检查所有可能的出现 majority element 的位置 [n/k,2n/k, .... ,n] ，在每个位置上根据当前元素做 search for range，O(log n)，如此重复最多 k 次即可。