public class Solution {
    public List<Integer> majorityElement(int[] nums) {
       List<Integer> ret = new LinkedList<Integer>();
       int c1=0,c2=0,n1=0,n2=0;
       for (int num:nums){
            if(num==c1)
                n1++;
            else if(num==c2)
                n2++;
            else if(n1==0){
                c1 = num;
                n1++;
            }
            else if(n2==0){
                c2 = num;
                n2++;
            }
            else{
                n1--;
                n2--;
            }
       }
       int count1 = 0;
       int count2 = 0;
       for(int num: nums){
            if(num==c1)
                count1++;
            // must be else if [0,0,0]
            else if(num==c2)
                count2++;
       }
       if(count1>nums.length/3)
           ret.add(c1);
       if(count2>nums.length/3)
           ret.add(c2);

        return ret;
    }
}

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums:
            return nums

        ret = []
        # two candidates
        n1 = 0
        n2 = 0
        # appear times for them
        c1 = 0
        c2 = 0

        for i in nums:
            # order is important
            if n1 == i:
                c1+=1
            elif n2 == i:
                c2+=1
            elif c1 == 0:
                c1 = 1
                n1 = i
            elif c2 == 0:
                c2 = 1
                n2 =i
            else:
                c1 -= 1
                c2 -= 1
        # count the appear time of two candidates
        if c1 != 0 and nums.count(n1) > len(nums)/3:
            ret.append(n1)
        if c2 != 0 and nums.count(n2)> len(nums)/3:
            ret.append(n2)
        return ret