【LeetCode】Majority Element 问题详解：从暴力到最优算法

在算法面试和LeetCode练习中，Majority Element（多数元素） 是一道经典题目。它的核心是寻找数组中出现次数超过 ⌊n/2⌋（n为数组长度）的元素。这个问题不仅考察对基础算法的掌握，更能体现你对时间/空间复杂度 trade-off 的理解。

比如，在投票系统中，我们需要快速找出获得超过半数选票的候选人；在数据挖掘中，多数元素可能代表最常见的异常值或趋势。掌握这个问题的解法，能帮你举一反三解决类似的“频率统计”问题。

目录#

问题描述#

LeetCode原题链接：169. Majority Element

题目要求：
给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊n/2⌋ 的元素。
说明：题目保证数组中一定存在多数元素。

解法1：暴力枚举（Brute Force）#

思路#

暴力枚举的核心是逐个检查每个元素的出现次数：

  1. 遍历数组中的每个元素 num；
  2. 再次遍历数组，统计 num 的出现次数；
  3. 如果次数超过 n/2，直接返回 num。

代码实现#

def majorityElement(nums):
    n = len(nums)
    half = n // 2  # 多数元素需要超过这个值
    for num in nums:
        count = 0
        for elem in nums:
            if elem == num:
                count += 1
            # 提前终止内层循环（优化）
            if count > half:
                break
        if count > half:
            return num

复杂度分析#

  • 时间复杂度：O(n²)。最坏情况下，每个元素都要遍历整个数组（比如数组是 [1,2,1,2,...,1]，最后一个元素是多数）。
  • 空间复杂度：O(1)。不需要额外空间。

优缺点#

  • 优点：逻辑简单，无需额外空间。
  • 缺点：效率极低，无法处理大规模数据（比如n=1e4时，需要1e8次运算）。

解法2：哈希表计数（Hash Map）#

思路#

哈希表的核心是用空间换时间：

  1. 用哈希表（字典）记录每个元素的出现次数；
  2. 遍历数组时更新哈希表，提前终止（当某元素的次数超过 n/2 时直接返回）。

代码实现（两种方式）#

方式1：用 collections.Counter 简化代码#

from collections import Counter
 
def majorityElement(nums):
    count = Counter(nums)
    # 取出现次数最多的元素（题目保证存在）
    return max(count, key=count.get)

方式2：手动维护哈希表（支持提前退出）#

def majorityElement(nums):
    count = {}
    half = len(nums) // 2
    for num in nums:
        count[num] = count.get(num, 0) + 1
        # 提前退出：一旦超过半数，直接返回
        if count[num] > half:
            return num

复杂度分析#

  • 时间复杂度：O(n)。最坏情况遍历整个数组（多数元素在最后一位），但平均情况更快（提前退出）。
  • 空间复杂度：O(n)。哈希表最多存储所有不同的元素（极端情况如所有元素唯一，但题目保证存在多数，所以实际存储量远小于n）。

优缺点#

  • 优点：代码简洁，时间效率高。
  • 缺点：需要额外空间存储哈希表，对内存敏感的场景不友好。

解法3：排序（Sorting）#

思路#

排序的核心是利用多数元素的位置特性：
如果数组已排序，多数元素必然出现在 ⌊n/2⌋ 的位置（无论n是奇数还是偶数）。
比如：

  • n=7（奇数）：排序后第3位（0-based）是多数元素（需要至少4次出现）；
  • n=6（偶数）：排序后第3位（0-based）是多数元素（需要至少4次出现）。

代码实现#

def majorityElement(nums):
    nums.sort()
    return nums[len(nums) // 2]

复杂度分析#

  • 时间复杂度：O(n log n)。排序的时间复杂度由排序算法决定（Python的list.sort()是Timsort，平均O(n log n)）。
  • 空间复杂度：O(1)（如果允许原地排序）或 O(n)（如果需要额外空间存储排序后的数组）。

优缺点#

  • 优点：代码极简，无需额外空间（原地排序）。
  • 缺点：时间复杂度高于哈希表和Boyer-Moore算法。

解法4：博伊尔-摩尔多数投票算法（Boyer-Moore Majority Vote Algorithm）#

引言#

这是最优解法，由Robert S. Boyer和J Strother Moore在1981年提出。它的核心优势是O(n)时间 + O(1)空间，完美解决了时间和空间的权衡问题。

算法思路#

算法维护两个变量：

  • candidate：当前候选的多数元素（初始为None）；
  • count：候选元素的“支持度”（初始为0）。

遍历数组时，遵循以下规则：

  1. 如果 count == 0：将当前元素设为新的 candidate；
  2. 如果当前元素等于 candidate：count += 1（支持度增加）；
  3. 否则：count -= 1（支持度减少）。

遍历结束后，candidate 就是多数元素。

关键直觉#

多数元素的出现次数超过所有其他元素的总和。因此，即使我们用“抵消”的方式（每遇到一个非候选元素就减少支持度），多数元素的支持度最终也会保持为正。

举个例子：nums = [2,2,1,1,1,2,2]

  • 候选元素2的支持度会被1抵消，但由于2的数量更多，最终候选元素仍为2。

代码实现#

def majorityElement(nums):
    candidate = None
    count = 0
    for num in nums:
        if count == 0:
            candidate = num  # 更换候选
        count += 1 if num == candidate else -1
    return candidate

复杂度分析#

  • 时间复杂度：O(n)。仅需遍历一次数组。
  • 空间复杂度：O(1)。仅用两个变量，完全不需要额外空间。

优缺点#

  • 优点：最优的时间和空间复杂度，适用于所有场景（尤其是内存受限的情况）。
  • 缺点：需要理解算法的核心逻辑（否则容易写错）。

解法对比与选择#

为了帮助你快速选择合适的解法，我们整理了各解法的关键指标：

解法时间复杂度空间复杂度适用场景
暴力枚举O(n²)O(1)小数据量，无需额外空间
哈希表（Counter）O(n)O(n)数据量中等，追求代码简洁
哈希表（提前退出）O(n)O(n)数据量较大，多数元素出现早
排序O(n log n)O(1)无需额外空间，允许O(n log n)时间
Boyer-Moore算法O(n)O(1)所有场景（最优）

常见陷阱与最佳实践#

常见陷阱#

  1. 排序时的索引错误：
    误用 len(nums)//2 - 1 代替 len(nums)//2。例如，nums = [2,2,1,1,1,2,2]（len=7），len//2=3 是正确索引，而 len//2-1=2 会返回1（错误）。

  2. 忘记提前退出：
    在哈希表解法中，没有提前终止循环，导致不必要的计算（比如多数元素在数组前半部分时，仍遍历整个数组）。

  3. 不理解Boyer-Moore的逻辑：
    随意修改算法逻辑（比如将 count 的初始值设为1），导致错误。例如，nums = [1] 时，初始 count=1 会正确返回1，但 nums = [2,1,2] 时会出错。

最佳实践#

  1. 优先选择Boyer-Moore算法：
    它是最优解法，适用于所有场景，尤其是内存受限的情况（比如嵌入式系统）。

  2. 测试边缘情况：

    • 单元素数组（nums = [5]）；
    • 所有元素相同（nums = [7,7,7]）；
    • 多数元素在数组末尾（nums = [1,2,3,4,5,5,5]）；
    • 交替元素（nums = [2,1,2,1,2]）。

  3. 理解算法的本质：
    不要死记硬背代码，要理解每种解法的逻辑。比如，Boyer-Moore的核心是“抵消”，哈希表的核心是“空间换时间”。

示例演练#

我们用 nums = [2,2,1,1,1,2,2] 演示所有解法的执行过程：

1. 暴力枚举#

  • 遍历元素2：统计出现次数为4（>3.5），直接返回2。

2. 哈希表（提前退出）#

  • 遍历2→count=1（未超过3.5）；
  • 遍历2→count=2（未超过）；
  • 遍历1→count=1（未超过）；
  • 遍历1→count=2（未超过）；
  • 遍历1→count=3（未超过）；
  • 遍历2→count=3（未超过）；
  • 遍历2→count=4（超过3.5），返回2。

3. 排序#

  • 排序后的数组：[1,1,1,2,2,2,2]；
  • len//2=3，返回索引3的元素2。

4. Boyer-Moore算法#

步骤当前元素candidatecount说明
1221count=0，设为候选
2222等于候选，count+1
3121不等于，count-1
4120不等于，count-1
5111count=0，更换候选为1
6210不等于，count-1
7221count=0，更换候选为2

遍历结束，candidate=2（正确）。

结论#

Majority Element问题的解法覆盖了算法设计的常见思路：暴力枚举、空间换时间、利用排序特性、贪心算法（Boyer-Moore）。其中，Boyer-Moore算法是最优解法，它的时间复杂度O(n)和空间复杂度O(1)使其适用于所有场景。

在面试中，面试官不仅考察你能否写出正确的代码，更看重你对算法的理解。比如，当被问到“为什么Boyer-Moore算法有效？”时，你可以解释：“多数元素的出现次数超过所有其他元素的总和，因此抵消后仍会保留。”

最后，建议你多练习类似的问题（比如LeetCode 229. Majority Element II），加深对频率统计问题的理解。

参考资料#

  1. LeetCode原题：169. Majority Element
  2. Boyer-Moore算法维基百科：Boyer–Moore majority vote algorithm
  3. GeekforGeeks：Majority Element
  4. Python官方文档：collections.Counter
2026-09