剑指 Offer 39. 数组中出现次数超过一半的数字

class Solution {
    
    public int majorityElement(int[] nums) {
    
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

利用此种方法是可以通过的，但显然Arrays.sort不是本题考察的重点。

摩尔投票法

class Solution {
    
    public int majorityElement(int[] nums) {
    
        int x = 0, votes = 0;
        for(int num : nums){
    
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }
}

题解