題目描述

給定一個大小為 n 的數(shù)組，找出其中所有出現(xiàn)超過 ? n/2 ? 次的元素。

分析：采用摩爾投票法，兩個階段：抵消階段和計數(shù)階段

抵消階段：兩個不同投票進行對抗，并且同時抵消掉各一張票，如果兩個投票相同，則累加可抵消的次數(shù)；

計數(shù)階段：在抵消階段最后得到的抵消計數(shù)只要不為 0，那這個候選人是有可能超過一半的票數(shù)的，為了驗證，則需要遍歷一次，統(tǒng)計票數(shù)，才可確定

public static int majorityElement(int[] nums) {
        int len = nums.length;

        if (len==0){
            return -1;
        }

        int major = 0;
        int vote = 0;

        for (int num:nums){
            if (vote==0){
                major = num;
                vote = 1;
            }else {
                if (major==num){
                    vote++;
                }else {
                    vote--;
                }
            }
        }
        if (vote==0){
            return -1;
        }

        int flag = 0;
        for (int num:nums){
            if (major == num){
                flag ++;
                if (flag>len/2){
                    return major;
                }
            }
        }
        return -1;
    }