N/3 Repeat Number

You’re given a read only array of n integers. Find out if any integer occurs more than n/3 times in the array in linear time and constant additional space.

If so, return the integer. If not, return -1.

If there are multiple solutions, return any one.

Input : [1 2 3 1 1]
Output : 1 
1 occurs 3 times which is more than 5/3 times.

思路:

Moore's Voting Algorithm，最多两个candiate，记录两个count。最后再check一遍是哪个candidate。

Solution:

Time: O(n)
Space: O(1)

public class Solution {
    // DO NOT MODIFY THE LIST
    public int repeatedNumber(final List<Integer> a) {
        if (a.size() <= 2) {
            return a.get(0);
        }
        Integer candidate1 = null;
        Integer candidate2 = null;
        int count1 = 0;
        int count2 = 0;
        for (int i = 0; i < a.size(); i ++) {
            Integer n = a.get(i);
            if (n.equals(candidate1)) {
                count1 ++;
            } else if (n.equals(candidate2)) {
                count2 ++;
            } else if (count1 == 0) {
                candidate1 = n;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = n;
                count1 = 1;
            } else {
                count1 --;
                count2 --;
            }
        }
        count1 = 0;
        count2 = 0;
        for (int i = 0; i < a.size(); i ++) {
            Integer n = a.get(i);
            if (n.equals(candidate1)) {
                count1 ++;
            } else if (n.equals(candidate2)) {
                count2 ++;
            }
        }
        if (count1 > a.size() / 3) {
            return candidate1;
        }
        if (count2 > a.size() / 3) {
            return candidate2;
        }
        return -1;
    }
}