剑指offer一刷：数学

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

难度：简单

方法一：哈希表统计法

遍历数组 nums，用 HashMap 统计各数字的数量，即可找出众数。此方法时间和空间复杂度均为 O(N)。

方法二：数组排序法

将数组 nums 排序，数组中点的元素一定为众数。

方法三：摩尔投票法

核心理念为票数正负抵消。此方法时间和空间复杂度分别为 O(N) 和 O(1)，为本题的最佳解法。

详细如下：

设输入数组 nums 的众数为 x，数组长度为 n。

推论一：若记众数的票数为 +1，非众数的票数为 -1，则一定有所有数字的票数和 > 0。

推论二：若数组的前 a 个数字的票数和 = 0，则 数组剩余 (n-a) 个数字的票数和一定仍 >0，即后 (n-a) 个数字的众数仍为 x。

根据以上推论，记数组首个元素为 n₁，众数为 x，遍历并统计票数。当发生票数和 = 0时，剩余数组的众数一定不变，这是由于：

• 当 n₁ = x： 抵消的所有数字，有一半是众数 x。
• 当 n₁ ≠ x： 抵消的所有数字，众数 x 的数量最少为 0 个，最多为一半。

利用此特性，每轮假设发生 票数和 = 0都可以缩小剩余数组区间。当遍历完成时，最后一轮假设的数字即为众数。

算法流程：

1. 初始化：票数统计 votes = 0，众数 x；
2. 循环：遍历数组 nums 中的每个数字 num；
   
   1. 当 票数 votes 等于 0，则假设当前数字 num 是众数；
   2. 当 num = x 时，票数 votes 自增 1；当 num != x 时，票数 votes 自减 1；
3. 返回值：返回 x 即可；

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;
    }
}

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/99ussv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(N)，空间复杂度：O(1)。