0169. Majority Element

题目信息

题号:
  1. 多数元素

难度:

Easy

主题:

数组、计数、排序、Boyer–Moore 投票

原题:

LeetCode 0169

重点:

利用严格过半保证,将不同元素成对抵消并把完整频次表压缩成候选与余额

题目重述

给定长度为 n 的整数数组 nums,返回其中的多数元素。多数元素的出现次数严格大于 floor(n / 2),题目保证它一定存在。

进阶目标是用 O(n) 时间和 O(1) 额外空间完成。

自建示例

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

2 出现 4 次,严格超过长度 7 的一半;扫描中的临时候选可以变化,最终仍回到 2。
输入:nums = [-5,3,-5,-5,3]
输出:-5

多数性的定义只依赖频次,与数值大小和正负无关。
输入:nums = [7]
输出:7

唯一元素出现 1 次,严格大于 floor(1 / 2) = 0。

C++ 实现

#include <algorithm>
#include <unordered_map>
#include <vector>

class Solution {
private:
    int repeatedCounting(const std::vector<int>& nums) {
        for (int candidate : nums) {
            int occurrences = 0;
            for (int value : nums) {
                if (value == candidate) {
                    ++occurrences;
                }
            }
            if (occurrences > static_cast<int>(nums.size()) / 2) {
                return candidate;
            }
        }
        return nums.front();
    }

    int frequencyTable(const std::vector<int>& nums) {
        std::unordered_map<int, int> occurrences;
        occurrences.reserve(nums.size());
        int threshold = static_cast<int>(nums.size()) / 2;

        for (int value : nums) {
            if (++occurrences[value] > threshold) {
                return value;
            }
        }
        return nums.front();
    }

    int sortedMiddle(std::vector<int> nums) {
        std::sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }

    int cancellationCandidate(const std::vector<int>& nums) {
        int candidate = 0;
        int balance = 0;

        for (int value : nums) {
            if (balance == 0) {
                candidate = value;
            }
            if (value == candidate) {
                ++balance;
            } else {
                --balance;
            }
        }
        return candidate;
    }

public:
    int majorityElement(std::vector<int>& nums) {
        return cancellationCandidate(nums);
    }
};

题解

从定义出发的重复计数

按定义,可以把每个位置的值都当作候选,再扫描整个数组统计其出现次数。 repeatedCounting 一定会找到题目保证存在的多数元素,但相同候选会被反复统计,最坏 时间为 O(n²)。瓶颈不在“判断是否相等”,而在没有保存此前已经得到的频次。

frequencyTable 用哈希表把每个值的计数保留下来。每读一个元素只增量更新一次;计数 首次超过 floor(n/2) 时可以立即返回,因为后续元素不会让该计数下降。这将期望时间 降为 O(n),代价是最多保存 O(n) 个不同值。

排序暴露了另一种结构

如果数组排好序,多数元素会形成长度超过 n/2 的连续块。这样长的块无论从哪里开始, 都必然覆盖下标 n/2,所以中间位置就是答案。sortedMiddle 不再维护全部频次, 但复制和排序需要 O(n) 空间与 O(n log n) 时间;若原地排序可以省去复制空间, 却会修改输入。

题目的“严格超过一半”还能提供更强的信息:多数元素的数量大于其余所有元素数量之和。 这允许不排序、不记频次,只不断删除互不相同的元素对。

成对抵消为何保持多数性

假设当前总长度为 N,真正多数元素出现 M 次,满足 M > N/2。删除两个不同 元素时:

  • 若其中一个是多数元素,新的计数和长度是 M-1、N-2,而 M-1 > (N-2)/2 与原不等式等价;

  • 若两者都不是多数元素,多数计数不变、总长度减少 2,多数性只会更强。

因此任意反复删除不同值对,都不会改变“剩余元素中的多数是谁”。真正多数元素不可能在 抵消完成后彻底消失;否则其余元素也至少要提供同样多的配对数量,与严格过半矛盾。

候选与余额压缩了哪些历史

cancellationCandidate 不真的删除数组元素。candidate 表示当前未配对元素的值, balance 表示该值尚未抵消的数量:

  • 当前值等于候选,无法与已有候选配成不同值对,余额加一;

  • 当前值不同,拿它与一个未配对候选抵消,余额减一;

  • 余额为零时,之前这个抵消段没有留下任何元素,当前值可以开启新的候选段。

完整哈希表中的每个频次被压缩成了两个标量。balance 不是候选在整个前缀中的真实 出现次数,而是当前抵消段中的净剩余票数;把它误解为总频次会无法解释候选为何能改变。

具体走读

对 [2,2,1,1,1,2,2]:

读入值  动作                         candidate  balance
2       余额为 0,选择 2;同值加票   2          1
2       同值加票                     2          2
1       异值抵消                     2          1
1       异值抵消                     2          0
1       余额为 0,选择 1;同值加票   1          1
2       异值抵消                     1          0
2       余额为 0,选择 2;同值加票   2          1

中途候选 2 的余额归零并不表示 2 已被证明不是多数,只表示已处理的那一段可以整体成对 删除。最后未被抵消的候选是 2;由题目保证存在多数元素,它必然就是真正多数。

存在性保证的重要性

Boyer–Moore 第一遍只产生“抵消后的候选”。若题目不保证多数元素存在,例如 [1,2,3],算法仍会返回某个候选,却不能证明它超过一半;此时必须再扫描一次验证 候选频次。本题已经明确保证存在,因此第二遍验证不会改变结果,可以省略。

方案选择与复杂度

重复计数时间 O(n²)、空间 O(1);哈希计数期望时间 O(n)、空间 O(n); 排序取中点时间 O(n log n),当前实现因复制数组使用 O(n) 空间。Boyer–Moore 只扫描一次,时间 O(n)、额外空间 O(1),同时满足进阶目标,因此主解采用 cancellationCandidate。