0169.多数元素

难度：🟢 简单

标签：数组、哈希表、分治、排序、计数

链接：169. 多数元素

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

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

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

解题思路

核心思想

本题的目标是找到数组中出现次数超过一半的元素。解决这个问题的核心思想有多种，但其中最巧妙且空间效率最高的是 摩尔投票法 (Boyer-Moore Voting Algorithm)。

思路选择

摩尔投票法 是解决此问题的最优思路。其核心理念是“对拼消耗”。

• 我们可以设想，把多数元素看作一方，把所有其他元素看作另一方。

• 从头开始遍历数组，我们维护一个候选元素 candidate 和一个计数器 count。

• 当遇到一个与 candidate 相同的数时，count 加一。

• 当遇到一个与 candidate 不同的数时，count 减一（相当于“同归于尽”）。

• 如果 count 减到 0，说明前面的数字已经完全被消耗掉了，我们就选择当前这个数作为新的 candidate，并重置 count 为 1。

由于多数元素的数量超过了所有其他元素数量之和，所以在对拼消耗之后，最终留下的 candidate 一定是那个多数元素。

关键步骤

1. 初始化：选择数组第一个元素 nums[0] 作为初始的候选人 candidate，计数器 count 初始化为 1。

2. 循环遍历：从第二个元素（索引 i = 1）开始遍历数组。 a. 如果当前元素 nums[i] 与 candidate 相同，则 count 加 1。 b. 如果当前元素 nums[i] 与 candidate 不同，则 count 减 1。 c. 如果 count 减为 0，则更换候选人，将 candidate 设为 nums[i]，并将 count 重新设为 1。

3. 返回结果：遍历结束后，candidate 中存储的就是多数元素，返回即可。

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
    let candidate = nums[0], count = 1;

    // 从第二个元素开始遍历
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === candidate) {
            // 遇到相同的数，计数加一
            count++;
        } else {
            // 遇到不同的数，计数减一
            count--;
            // 如果计数归零，更换候选人
            if (count <= 0) {
                candidate = nums[i];
                count = 1;
            }
        }
    }

    return candidate;
};

复杂度分析

• 时间复杂度：O(n) 其中 n 是数组 nums 的长度。我们只需要对数组进行一次完整的遍历。

• 空间复杂度：O(1) 我们只使用了 candidate 和 count 两个额外变量，空间消耗是恒定的。

相关题目

• 0229.多数元素 II

• 0001.两数之和

总结

本题的摩尔投票算法是一个非常精妙的解法，它通过一种“对抗消耗”的思路，在一次遍历和常数空间内找到了多数元素。这个算法是处理“寻找出现次数超过特定阈值的元素”这类问题的强大工具。