Leetcode #229 Majority Element I

public static List<Integer> majorityElement(int[] nums) {
         if(nums.length==0)
                return new LinkedList<>();
        List<Integer> ls = new LinkedList<>();
        int num1=nums[0],num2=nums[0],cnt1=0,cnt2=0;
        for(int i=0,len=nums.length;i<len;i++){
            if(nums[i]==num1)
                cnt1++;
            else if(nums[i]==num2){
                cnt2++;
            }
            else if(cnt1==0){
                num1=nums[i];
                cnt1=1;
            }
            else if(cnt2==0){
                num2 = nums[i];
                cnt2=1;
            }
            else {
                cnt1--;
                cnt2--;
            }
        }
        cnt1=0;
        cnt2=0;
        for(int i=0,len=nums.length;i<len;i++){
            if(nums[i]==num1)
                cnt1++;
            else if(nums[i]==num2){
                cnt2++;
            }
        }
        if(cnt1>nums.length/3)
            ls.add(num1);
        if(cnt2>nums.length/3)
            ls.add(num2);
        System.out.println(cnt1+" "+num1);
        System.out.println(cnt2+" "+num2);
        return ls;
    }

首先，一个数组中出现次数大于n／3的数字最多只可能有两个，所以建立两个候选数字。
再遍历数组，若和其中一个候选数字相同，则计数+1，否则-1。