剑指Offer题解 - Day51

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

力扣题目链接[1]

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

「示例 1:」

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

「限制：」

1 <= 数组长度 <= 50000

思路：

如果说，将数组进行排序，那么出现次数超过一半的数字肯定位于数组的中位数。

中位数

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let result = nums.sort((a, b) => a - b) // 排序
    return result[Math.floor(nums.length / 2)] // 获取中位数
};

分析：

本方法是最简单易懂的方法，但是直接使用API来题解不能达到出题者的目的。因此还需要寻找更优解。

哈希表

同样的，我们可以用哈希表来存储每个数字出现的次数，然后找出出现次数最多的即可。该方法的时间复杂度和空间复杂度均为O(n) 。

摩尔投票法

该方法的原理是票数的正负抵消。从而获取到出现次数超过一半的数字。

首先寻找规律，首先称出现次数超过一半的数字为 「众数」 ：

• 如果是众数则投票 「+1」 ，如果不是众数则投票 「-1」 ，最后的结果一定 「大于0」 ；
• 如果数组的前面部分数字的票数和为 「0」 ，则剩余数字的票数和一定 「大于0」，并且众数依旧不变 ****；

根据上述两条规律，可以根据投票数为 「0」 不断缩小数组的范围，最终剩余的数字就是 「众数」 。

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let res = 0; // 初始化众数为0
    let votes = 0; // 初始化投票数为0
    for (const num of nums) {
        if (votes === 0) res = num; // 当投票数为0时，假设当前元素就是众数
        votes += num === res ? 1 : -1; // 投票
    }
    return res; // 返回众数
};

• 时间复杂度 O(n)。
• 空间复杂度 O(1)。

分析：

核心思路是：当投票数为0时，假设当前元素就是众数。然后根据投票规则进行投票：如果是众数则投票 「+1」 ，如果不是众数则投票 「-1」 。

当下次遇到投票数为 「0」 时，前面所有的元素就可以丢弃了，因为这意味着众数还在剩余元素里面。此时继续假设当前元素为众数，执行投票的逻辑。

直到遍历完数组，最终的结果res就是众数。然后返回res即可。

由于需要遍历整个数组，因此时间复杂度是O(n)，声明常数级别的变量占用O(1)的空间。

总结

本题既可以排序取中位数，又可以通过哈希表统计出现次数。效率最高的办法是第三种：投票法。通过正负抵消的方式，最终留下来的就是众数。

参考资料

[1]力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/99iy4g/