[LintCode] 47 Majority Number II 解题报告

Description
Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array.

Find it.


Notice
There is only one majority number in the array.


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


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


思路
Majority Number I 的扩展。
只有可能有2个数字的频率大于1/3。我们设2个Candidate和2个count。
分析和I是一样的。
假设到最后count一直大于1，那么就在最初的2个Candidate里找。
如果某个count等于0。如果M不在之前遍历过的元素里，那么就在后面继续找。
如果M在，假设遍历过x个元素，那么M最多出现过x / 3次。后面必须要满足M至少出现n / 3 + 1 - x / 3 = (n - x) / 3 + 1次。这不还是在后面的数里找一个众数么。

最后两个Candidate里只有一个才是M。我们再遍历一次，找频率最高的那个。




Code

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: The majority number that occurs more than 1/3
     */
    public int majorityNumber(ArrayList<Integer> nums) {
        // write your code
        int major1 = 0;
        int major2 = 1; // must give major2 a different value
        int count1 = 0;
        int count2 = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            int num = nums.get(i);
            if (num == major1) {
                count1++;
            }
            else if (num == major2) {
                count2++;
            }
            else if (count1 == 0) {
                major1 = num;
                count1++;
            }
            else if (count2 == 0) {
                major2 = num;
                count2++;
            }
            else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            int num = nums.get(i);
            if (num == major1) {
                count1++;
            }
            if (num == major2) {
                count2++;
            }
        }
        
        if (count1 > count2) {
            return major1;
        }
        return major2;
    }
}