045 · Majority Element

My First Thoughts

这题有点像求 mode，也就是众数。

但它又不是普通的“找出现次数最多的元素”。普通众数只要计数，然后选出出现次数最大的那个就行。

这题额外给了一个更强的条件：

多数元素一定存在，并且出现次数大于 nums.length / 2。

这就让问题更简单一些。因为不需要比较所有数字里“谁最多”，只要找到谁超过一半。

首先能想到的就是遍历数组，计算每个数字出现的次数。谁的次数超过一半，谁就是答案。这应该是这题最底层的逻辑。

进一步想，如果某个数字在遍历过程中已经超过一半，那它一定就是答案，也许可以提前退出。

不过如果每一步都去找“当前谁最多”，或者每次都把当前最多的数字拿出来比较，反而会让逻辑变重。

所以可以考虑只做一件事：遍历时把每个数字的次数加进哈希表，先不管谁最多。等计数结束后，再扫一遍哈希表，找出超过一半的数字。

代码就是：

counts = {}

length = len(nums)
half = length / 2

for i in range(0, length):
    val = nums[i]
    counts[val] = counts.get(val, 0) + 1

for key, value in counts.items():
    if value > half:
        return key

这个方法很简单直接：

• counts 记录每个数字出现的次数
• half 表示数组长度的一半
• 第二轮只要发现某个数字的次数大于 half，就返回它

因为题目保证多数元素一定存在，所以这个哈希计数法一定能找到答案。

那这题考的是什么呢？

---

Why That Is Not Enough

这个解法本身是正确的。

它的问题不是逻辑错，也不是不够清楚，而是用了额外的哈希表空间。

如果只是要通过这道题，哈希计数已经足够。只是这题给的“超过一半”条件很特殊，所以还能进一步利用这个条件：不保存所有数字的次数，只用一个候选值和一个计数器，最后找出多数元素。

这个方法叫 Boyer-Moore Voting Algorithm，通常翻译成“摩尔投票法”。

---

Final Idea

因为多数元素出现次数超过一半，所以它可以和其他所有元素一一抵消之后，仍然剩下来。

我们维护两个变量：

candidate  当前候选的多数元素
count      这个候选元素当前的票数

遍历 nums：

• 如果 count == 0，说明前面的元素已经抵消完了，把当前数字设为新的 candidate
• 如果当前数字等于 candidate，count += 1
• 如果当前数字不等于 candidate，count -= 1

最后留下来的 candidate 就是多数元素。

---

Why It Works

可以把这个过程理解成“配对抵消”。

当一个数字和当前候选数字不同，就让它们互相抵消一次。

由于真正的多数元素出现次数大于数组长度的一半，即使它和所有其他数字都抵消，最后也不可能被完全抵消掉。

所以当题目保证多数元素一定存在时，最后留下来的候选值就是答案。

比如：

nums = [2, 2, 1, 1, 1, 2, 2]

过程可以理解为：

2 和 1 抵消
2 和 1 抵消
剩下的 2 更多

最后候选值会回到 2。

---

Code

def majorityElement(nums):
    candidate = None
    count = 0

    for num in nums:
        if count == 0:
            candidate = num

        if num == candidate:
            count += 1
        else:
            count -= 1

    return candidate

---

Complexity

Time	\(O(n)\) - 只遍历数组一次
Space	\(O(1)\) - 只使用 candidate 和 count 两个变量

---

Takeaway

如果题目只要求找出现次数超过一半的元素，哈希计数是最直接的底层逻辑；如果想进一步优化空间，可以利用“多数元素一定存在”这个条件，把不同元素互相抵消，最后留下来的就是答案。

---

← Quiz