Majority Element II

Q:
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.
A:
最多2个结果。那么每次删除3个即可。   (这道题目有问题，OJ是要求大于等于 ⌊ n/3 ⌋ )
***********下面这个方法思路是有问题的 *********************

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new LinkedList();
        int n1 = 0,n2 = 0;
        int c1 = 0,c2=0;// count of n1,n2,n3
        for(int i = 0;i<nums.length;i++){
            int val = nums[i];
            if(c1==0){ // if first value is not found
                n1 = val;
                c1=1;
            }else if( c2 ==0){ // if second value is not found
                n2 = val;
                c2=1;
            }else{ // already found two different values
                if(val == n1){
                    c1++;
                }else if(val == n2){
                    c2++;
                }else{ // not equals to previous two val
                    c1--;
                    c2--;
                }
            }
        }
        // now check two possible value, n1 and n2;
        if(c1>0)
            checkValue(list, nums,n1);
        if(c2>0 && n1 != n2) // for po
            checkValue(list, nums,n2);
        return list;
    }
    private void checkValue(List<Integer> list, int[] nums, int value){
        int count = 0;
        for(int i =0;i<nums.length;i++){
            if(nums[i] == value)
                count++;
        }
        if(count > nums.length/3)
            list.add(value);
    }
}

**************这个是正确的解法*******************

public class Solution { 
    public List<Integer> majorityElement(int[] nums) {
        int a = 0,b=0, aCount = 0, bCount = 0;
        for(int val : nums){
            if(aCount==0 || val == a){
                aCount++;
                a = val;
            }else if(bCount==0 || val == b){
                bCount++;
                b = val;
            }else{// found both a, b and c different
                bCount--;
                aCount--;
                if(aCount==0){ // since we always check aCount/a firstly
                    aCount = bCount;
                    a = b;
                    bCount =0;
                }
            }
        }
        List<Integer> res = new LinkedList();
        if(aCount > 0 && isMoreThanThird(nums,a))
            res.add(a);
        if(bCount > 0 && isMoreThanThird(nums,b))
            res.add(b);
        return res ;
    }
    private boolean isMoreThanThird(int[] nums, int a){
        int count = 0;
        for(int x : nums)
            if( x == a)
                count++;
        return count > nums.length/3;
    }
}

Mistakes:
1：  在于for loop中各个 检测语句， 不产生重复。  (因此，当检查c2==0的时候，前面要检查是否已经是n1的值了。
2:  最后n2的时候，要有个if语句