169. 多数元素

LeetCode 169¹ · 简单 · 技巧

题

给一个长度为 n 的数组，其中有一个元素出现次数严格大于 n / 2，找出它。进阶要求线性时间、常数空间。

例：nums = [2, 2, 1, 1, 1, 2, 2] → 2。

一句话

维护一个候选和票数：遇到同一个数票数 +1，不同 -1，票数归零就换当前数当候选；扫完剩下的候选就是答案。

关键技巧

抵消论证。 每次「票数 -1」相当于从数组里删掉一对不同的数。删掉一对不同的数后，多数元素仍是剩余部分的多数——这一对里至多有一个是它，它的占比不降。一直删到不能再删，剩下的只能全是同一个数，而多数元素不可能被删光（它比其余所有数加起来还多），所以剩下的就是它。

为什么票数归零时换候选不亏。 归零意味着目前扫过的前缀已经被两两抵消干净，前缀里任何数都没有超过一半——多数元素在剩余后缀里依然过半，对后缀重新开始投票即可。

前提很重要。 投票法只在「保证存在多数元素」时直接返回；不保证时要再扫一遍验证候选的出现次数。

其他解法对比。 排序取中位数 \(O(n\log n)\)；哈希计数 \(O(n)\) 空间；按位统计（每一位上多数元素的位值也占多数）\(O(32n)\) 时间 \(O(1)\) 空间。

解

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        cand, votes = None, 0
        for x in nums:
            if votes == 0:
                cand = x          # 前缀已抵消干净，重新选候选
            votes += 1 if x == cand else -1
        return cand

时间 \(O(n)\)，空间 \(O(1)\)。

延伸

• 超过 n/3 的元素（LeetCode 229）：至多 2 个，维护两个候选同时投票，最后必须验证。
• 「抵消」的另一种形态：136. 只出现一次的数字 用异或让成对的数自我抵消。
• 中位数视角：多数元素一定是排序后下标 n // 2 的那个——可以用 215. 数组中的第K个最大元素 的快速选择 \(O(n)\) 求出。

s = Solution()
assert s.majorityElement([3, 2, 3]) == 3
assert s.majorityElement([2, 2, 1, 1, 1, 2, 2]) == 2
assert s.majorityElement([7]) == 7
assert s.majorityElement([1, 2, 1, 3, 1]) == 1