Majority Number II

Question

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.

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

Note
There is only one majority number in the array.

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

Analysis

与Majority Number问题相似，最直观的想法就是，建立HashMap，记录list中的每一个integer元素的个数，如果大于1/3list长度，即可返回。

由于此时只要求大于1/3，Moore的方法需要稍加改变。满足大于[1/3]的数，应当小于等于2个，也就是说，需要maintain两个top number作为candidate。

时间 O(n)，空间 O(1)

Solution

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) {
        int count1 = 0, count2 = 0;
        int candidate1 = 0, candidate2 = 0;
        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        count1 = count2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i) == candidate1) {
                count1++;
            } else if (nums.get(i) == candidate2) {
                count2++;
            }
        }
        return count1 > count2 ? candidate1 : candidate2;
    }
}