image.png

解法

神奇的解法，因为要返回的数，要超过半数，所以相同加1，不同减1，最终count应该是大于0的，所以可以这样去求解。

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

剩下的常规解法，可以用map去维护出现的次数，发现超过半数的直接返回就好啦，不过这样空间复杂度不是O(1)