leetcode 229: Majority Element II

leetcode 229: Majority Element II

Majority Element II

Given an integer array of size n, find all elements that appear more than⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

[思路]

觀察可知，數組中至多可能會有2個出現次數超過 ⌊ n/3 ⌋ 的眾數

記變量n1, n2為候選眾數； c1, c2為它們對應的出現次數

遍歷數組，記當前數字為num

若num與n1或n2相同，則將其對應的出現次數加1

否則，若c1或c2為0，則將其置為1，對應的候選眾數置為num

否則，將c1與c2分別減1

最後，再統計一次候選眾數在數組中出現的次數，若滿足要求，則返回之。

[CODE]

public class Solution {
    public List majorityElement(int[] nums) {
        // 1, 2
        List res = new ArrayList<>();
        if(nums==null || nums.length==0) return res;
        if(nums.length==1) {
            res.add(nums[0]);
            return res;
        }
        
        int m1 = nums[0];
        int m2 = 0;
        
        int c1 = 1;
        int c2 = 0;
        
        for(int i=1; inums.length/3) res.add(m1);
        if(c2>nums.length/3) res.add(m2);
        return res;
    }
}