[LintCode] 46 Majority Number 解题报告

Description
Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.


Example
Given [1, 1, 1, 1, 2, 2, 2], return 1


Challenge
O(n) time and O(1) extra space


思路
贪心法可以做到O(n)。这题的算法其实是叫Boyer-Moore majority vote algorithm。
我们遍历一遍数组，假设当前值就是majority number。
我们同时维护一个从0开始的count。
当下一个数和当前的majority number相等时，count++，否则count--。
当count为0的时候表示遍历过的这些数字中，我们选定的majority number正好占一半。所以我们可以把前面这些数字全部丢掉不用管了。
下一个数字，我们把它设成majority number，然后接着做。
当我们遍历完整个数组的时候，剩下的这个数字就是majority number了。

以上。。。完全没说清楚。。。
再来。。。

遍历数组，假设当前值就是Candidate M，count初始值0。如果遍历到的数和Candidate相等，count++，反正count--。
会碰到两种情况：
1. 遍历到最后，count始终大于0。这说明我们的Candidate一直是A[0]，没换过。那么A[0]就是我们要找的M。
2. 遍历到某一个点，count变成0了。还是分2种情况讨论：
    a. 如果M在遍历过的点里没有出现过。很简单，在后面的点里找一个Majority Number出来就是M。
    b. 如果M在遍历过的点里出现过。假设这时候我们已经遍历过x个点，还剩n - x个点。那么在这x个点里，M最多出现过x / 2次。M在整个数组里至少出现n / 2 + 1次。所以说，在还没有遍历过的点里，M最少还需要出现过 n / 2 + 1 - x / 2次。化简一下，M在后面至少出现(n - x) / 2 + 1次。这是什么意思：在后面的点里找一个Majority Number出来，就是M。
    总结一下情况a和b。当count变成0的时候，就在没有遍历过的点里重新找出一个M，就是整个数组的Majority Number了。




Code

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: find a  majority number
     */
    public int majorityNumber(ArrayList<Integer> nums) {
        // write your code
        int majority = 0;
        int count = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i) == majority) {
                count++;
            }
            else if (count == 0) {
                majority = nums.get(i);
                count++;
            }
            else {
                count--;
            }
        }
        return majority;
    }
}