如何找出数组中出现次数超过一半的数字？-Python教程-PHP中文网

摩尔投票算法能高效找出数组中出现次数超过一半的数字，其核心是通过抵消机制在O(n)时间与O(1)空间内锁定候选者，最终遍历验证其合法性。

如何找出数组中出现次数超过一半的数字？

要找出数组中出现次数超过一半的数字，最优雅且高效的方法无疑是摩尔投票算法（Moore's Voting Algorithm）。它以一种巧妙的“抵消”机制，能够在只遍历一次数组的情况下，用极小的额外空间找到这个特殊的数字。

解决方案

解决这类问题，我个人最偏爱摩尔投票算法。它的核心思想其实非常直观：如果你有一个元素，它的出现次数超过了数组总长度的一半，那么即使你让它和所有其他不同的元素“同归于尽”，它也一定能笑到最后。

具体操作起来，我们维护两个变量：一个

candidate

登录后复制

（候选者）和一个

count

登录后复制

（计数器）。

初始化
```
candidate
```
登录后复制
为数组的第一个元素，
```
count
```
登录后复制
为1。
遍历数组的其余部分： a. 如果
```
count
```
登录后复制
变为0，这意味着当前的
```
candidate
```
登录后复制
已经被前面那些非它的元素“抵消”完了。此时，我们将当前的数组元素设为新的
```
candidate
```
登录后复制
，并将
```
count
```
登录后复制
重置为1。 b. 如果当前元素与
```
candidate
```
登录后复制
相同，
```
count
```
登录后复制
加1。 c. 如果当前元素与
```
candidate
```
登录后复制
不同，
```
count
```
登录后复制
减1。
遍历结束后，
```
candidate
```
登录后复制
就是我们要找的那个出现次数超过一半的数字。

为什么这个方法管用？ 因为它利用了多数元素的特性。假设多数元素是M，少数元素是X。无论M和X如何交错出现，M的数量总是多于X的总和。当M与X相互抵消时，最终M一定会剩下。这个过程，就像一场多数派的“胜利”。

例如，数组

[2, 1, 2, 3, 2, 2]

登录后复制

```
candidate = 2
```
登录后复制
,
```
count = 1
```
登录后复制
遇到
```
1
```
登录后复制
：
```
1 != 2
```
登录后复制
，
```
count = 0
```
登录后复制
。此时，
```
candidate
```
登录后复制
被抵消，新的
```
candidate = 1
```
登录后复制
,
```
count = 1
```
登录后复制
。
遇到
```
2
```
登录后复制
：
```
2 != 1
```
登录后复制
，
```
count = 0
```
登录后复制
。
```
candidate
```
登录后复制
被抵消，新的
```
candidate = 2
```
登录后复制
,
```
count = 1
```
登录后复制
。
遇到
```
3
```
登录后复制
：
```
3 != 2
```
登录后复制
，
```
count = 0
```
登录后复制
。
```
candidate
```
登录后复制
被抵消，新的
```
candidate = 3
```
登录后复制
,
```
count = 1
```
登录后复制
。
遇到
```
2
```
登录后复制
：
```
2 != 3
```
登录后复制
，
```
count = 0
```
登录后复制
。
```
candidate
```
登录后复制
被抵消，新的
```
candidate = 2
```
登录后复制
,
```
count = 1
```
登录后复制
。
遇到
```
2
```
登录后复制
：
```
2 == 2
```
登录后复制
，
```
count = 2
```
登录后复制
。最终，
```
candidate
```
登录后复制
是2。

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

    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1

    # 如果题目保证存在，这一步就足够了。
    # 如果不保证，还需要第二遍遍历验证candidate的实际出现次数。
    return candidate

# 示例
# arr = [1, 2, 3, 2, 2, 2, 5, 2]
# print(find_majority_element(arr)) # 输出 2

登录后复制

摩尔投票算法的效率优势在哪里？

每次我思考这类“多数元素”问题时，摩尔投票算法总是第一个跳入脑海。它的核心魅力在于其无与伦比的效率。我们来看它的时间复杂度和空间复杂度：

时间复杂度：O(n)。我们只需要遍历数组一次。无论数组有多大，处理每个元素的时间都是常数，所以总时间与数组长度成正比。这在处理大数据集时至关重要。
空间复杂度：O(1)。我们只用了两个变量（
```
candidate
```
登录后复制
和
```
count
```
登录后复制
）来存储状态。这意味着无论数组有多长，我们需要的额外内存空间都是固定的，与输入规模无关。

这种O(n)时间、O(1)空间的能力，在算法世界里简直是“圣杯”级别的表现。相比之下，其他方法，比如先排序再取中间元素（O(n log n)时间），或者用哈希表计数（O(n)时间，O(n)空间），都无法同时达到这样的极致效率。摩尔投票算法之所以高效，正是因为它巧妙地利用了多数元素的“数量优势”，避免了复杂的存储和比较。它不是在“找”这个数，而是在“淘汰”掉所有非多数元素的过程中，让多数元素自然浮现。

多数元素不存在时，摩尔投票算法会给出什么结果？

这是一个很关键的问题，也是摩尔投票算法的一个“小陷阱”或者说需要注意的细节。如果题目明确保证数组中一定存在出现次数超过一半的数字，那么摩尔投票算法的单次遍历结果就是正确的。但如果这个前提不成立，也就是说，数组中可能不存在这样的多数元素，那么摩尔投票算法在第一遍遍历结束后，

candidate

登录后复制

变量中存储的，仅仅是一个“候选者”，它不一定就是真正的多数元素。

举个例子：数组

[1, 2, 3, 4, 5]

登录后复制

。这里面没有出现次数超过一半的数字。

```
candidate = 1
```
登录后复制
,
```
count = 1
```
登录后复制
遇到
```
2
```
登录后复制
：
```
count = 0
```
登录后复制
，
```
candidate = 2
```
登录后复制
,
```
count = 1
```
登录后复制
遇到
```
3
```
登录后复制
：
```
count = 0
```
登录后复制
，
```
candidate = 3
```
登录后复制
,
```
count = 1
```
登录后复制
遇到
```
4
```
登录后复制
：
```
count = 0
```
登录后复制
，
```
candidate = 4
```
登录后复制
,
```
count = 1
```
登录后复制
遇到
```
5
```
登录后复制
：
```
count = 0
```
登录后复制
，
```
candidate = 5
```
登录后复制
,
```
count = 1
```
登录后复制
最终，算法会返回
```
5
```
登录后复制
。但显然，
```
5
```
登录后复制
并不是多数元素。

再比如：数组

[1, 1, 2, 2, 3]

登录后复制

。也没有多数元素。

怪兽AI数字人

数字人短视频创作，数字人直播，实时驱动数字人

查看详情

```
candidate = 1
```
登录后复制
,
```
count = 1
```
登录后复制
遇到
```
1
```
登录后复制
：
```
candidate = 1
```
登录后复制
,
```
count = 2
```
登录后复制
遇到
```
2
```
登录后复制
：
```
candidate = 1
```
登录后复制
,
```
count = 1
```
登录后复制
遇到
```
2
```
登录后复制
：
```
candidate = 1
```
登录后复制
,
```
count = 0
```
登录后复制
遇到
```
3
```
登录后复制
：
```
candidate = 3
```
登录后复制
,
```
count = 1
```
登录后复制
最终返回
```
3
```
登录后复制
。同样不正确。

所以，当不确定多数元素是否存在时，我们需要在摩尔投票算法的第一遍遍历结束后，再进行第二次遍历。这次遍历的目的是统计

candidate

登录后复制

在原数组中实际出现的次数。如果这个次数确实超过了数组长度的一半，那么它就是我们要找的数字；否则，就说明数组中不存在这样的多数元素。

def find_majority_element_robust(nums):
    if not nums:
        return None # 或者抛出异常，根据具体需求

    candidate = None
    count = 0

    # 第一遍：找出候选者
    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1

    # 第二遍：验证候选者是否真的是多数元素
    actual_count = 0
    for num in nums:
        if num == candidate:
            actual_count += 1

    if actual_count > len(nums) // 2:
        return candidate
    else:
        return None # 或者其他指示，表示不存在

登录后复制

这种两遍遍历的方法，虽然多了一次遍历，但总时间复杂度依然是O(n)，空间复杂度保持O(1)，提供了更强的鲁棒性。

除了摩尔投票，其他解决思路的优劣对比？

在解决“找出数组中出现次数超过一半的数字”这个问题时，除了摩尔投票算法，我们当然还有其他方法。每种方法都有其适用场景和优缺点，理解这些能帮助我们根据具体需求做出最佳选择。

哈希表（Hash Map / Dictionary）计数法：
- 思路： 遍历数组，用一个哈希表记录每个数字出现的次数。然后遍历哈希表，找出计数超过
```
len(nums) // 2
```
  登录后复制
  的那个数字。
- 优点：
  - 思路直观，容易理解和实现。
  - 可以轻松应对“找出出现次数超过 k 的所有数字”这类更通用的问题。
  - 时间复杂度为 O(n)，因为哈希表的插入和查找操作平均是 O(1)。
- 缺点：
  - 空间复杂度为 O(n)，在最坏情况下（所有数字都不同），哈希表需要存储所有元素。这对于内存受限的场景可能不适用。
- 个人看法： 如果不考虑空间限制，或者数据规模不大，哈希表是个非常稳妥的选择。它就像一个“万金油”，虽然不是最极致的，但很可靠。
排序法：
- 思路： 将数组排序。如果存在一个数字出现次数超过一半，那么排序后，它一定会出现在数组的中间位置（
```
nums[len(nums) // 2]
```
  登录后复制
  ）。
- 优点：
  - 思路简单，实现也相对容易，很多语言都内置了高效的排序函数。
  - 如果数组本身就需要排序，那么这个方法几乎没有额外开销。
  - 空间复杂度通常是 O(1)（如果原地排序）或 O(n)（如果使用非原地排序算法）。
- 缺点：
  - 时间复杂度是 O(n log n)，这是由排序算法决定的。对于非常大的数据集，这比摩尔投票的 O(n) 要慢。
- 个人看法： 当数组规模适中，或者对时间复杂度要求不是极致，且希望代码简洁时，排序法是一个不错的选择。尤其是在面试中，如果一时想不起摩尔投票，排序法也能快速给出正确答案。
分治法（Divide and Conquer）：
- 思路： 将数组分成两半，递归地找出左右两半的多数元素。如果左右两半的多数元素相同，那就是整个数组的多数元素。如果不同，就需要统计这两个候选者在整个数组中的出现次数。
- 优点：
  - 理论上是一种解决问题的通用范式。
  - 可以并行化处理。
- 缺点：
  - 实现起来相对复杂，边界条件和合并逻辑需要仔细处理。
  - 最坏情况下的时间复杂度仍是 O(n log n)。
  - 通常不如摩尔投票算法直接和高效。
- 个人看法： 这种方法更偏向于理论探讨和算法设计练习，在实际解决这个特定问题时，效率和简洁性都不及摩尔投票。