Adrian Wang's blog

一个完全由AI生成，但是内容高质量的Blog

LeetCode 169 - 多数元素（Majority Element）

Posted on Edited on In , ,
Symbols count in article: 4.5k Reading time ≈ 4 mins.
详解四种解决多数元素问题的方法：哈希表计数法、排序法、分治法和摩尔投票算法，全面分析各种解法的时间复杂度和空间复杂度

问题描述

给定一个大小为 n 的数组 nums，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

1
2
输入：[3,2,3]
输出：3

示例 2：

1
2
输入：[2,2,1,1,1,2,2]
输出：2

约束条件：

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9
  • 题目数据保证 nums 中存在多数元素

解题思路

针对多数元素问题，我们有多种解决方案。下面我们将详细介绍四种常用的解法：

方法一：哈希表计数法

核心思想：使用哈希表记录每个元素出现的次数，找出出现次数大于 n/2 的元素。

这是一种直观的解法，通过两次遍历实现：

  1. 第一次遍历：统计每个元素的出现次数
  2. 第二次遍历：找出出现次数大于 n/2 的元素

方法二：排序法

核心思想：如果将数组排序，由于多数元素出现次数大于 n/2，所以排序后中间位置的元素一定是多数元素。

这是一种简单但效率不高的解法：

  1. 对数组进行排序
  2. 返回中间位置的元素（下标为 n/2）

方法三：分治法

核心思想：将数组分为左右两部分，分别找出左右两部分的多数元素，然后确定整个数组的多数元素。

分治法的具体步骤：

  1. 将数组分成左右两部分
  2. 递归地找出左半部分和右半部分的多数元素
  3. 比较这两个多数元素在整个数组中的出现次数，返回出现次数较多的那个

方法四：摩尔投票法

核心思想：利用"不同元素相互抵消"的思想，找出最终留下的元素。

想象一下有两支军队在打仗：

  • 红军（代表多数元素）
  • 蓝军（代表所有其他元素）

由于多数元素出现次数超过总数的一半，所以红军人数必然多于蓝军。即使红蓝双方一对一厮杀（相互抵消），最后战场上剩下的一定是红军！

这就是摩尔投票算法的核心思想：不同的数字相互抵消，最后剩下的一定是出现次数最多的那个数字。

算法步骤（超简单版）

  1. 找一个"候选人"，先认为第一个数字是候选人
  2. 开始计数：遇到和候选人一样的数字就+1，遇到不一样的就-1
  3. 如果计数变成0了，就换一个候选人（选当前遇到的那个数字）
  4. 继续上面的过程直到结束
  5. 最后的候选人就是我们要找的多数元素

实现细节与代码

方法一：哈希表计数法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func majorityElement(nums []int) int {
    // 创建哈希表，用于统计每个元素出现的次数
    countMap := make(map[int]int)
    
    // 统计每个元素出现的次数
    for _, num := range nums {
        countMap[num]++
    }
    
    // 找出出现次数大于 n/2 的元素
    threshold := len(nums) / 2
    for num, count := range countMap {
        if count > threshold {
            return num
        }
    }
    
    // 因为题目保证有多数元素，所以不会走到这里
    return -1
}

示例演示：以 [2,2,1,1,1,2,2] 为例

  1. 初始化 countMap = {}
  2. 遍历数组并统计：
    • 遇到 2：countMap[2] = 1
    • 遇到 2：countMap[2] = 2
    • 遇到 1：countMap[1] = 1
    • 遇到 1：countMap[1] = 2
    • 遇到 1：countMap[1] = 3
    • 遇到 2：countMap[2] = 3
    • 遇到 2：countMap[2] = 4
  3. 最终 countMap = {1: 3, 2: 4}，阈值 threshold = 7/2 = 3
  4. 检查 countMap 中元素，发现 2 的出现次数为 4，大于阈值 3
  5. 返回 2 作为多数元素

方法二：排序法

1
2
3
4
5
6
7
8
9
10
import "sort"

func majorityElement(nums []int) int {
    // 对数组进行排序
    sort.Ints(nums)
    
    // 返回中间位置的元素
    // 由于多数元素出现次数大于 n/2，排序后中间位置一定是多数元素
    return nums[len(nums)/2]
}

示例演示：以 [2,2,1,1,1,2,2] 为例

  1. 排序后数组变为 [1,1,1,2,2,2,2]
  2. 中间位置是 7/2 = 3，对应的元素是 nums[3] = 2
  3. 返回 2 作为多数元素

方法三：分治法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func majorityElement(nums []int) int {
    return majorityElementRec(nums, 0, len(nums)-1)
}

func majorityElementRec(nums []int, lo, hi int) int {
    // 基本情况：只有一个元素
    if lo == hi {
        return nums[lo]
    }
    
    // 将数组分成两半
    mid := lo + (hi - lo)/2
    
    // 分别找出左右两部分的多数元素
    left := majorityElementRec(nums, lo, mid)
    right := majorityElementRec(nums, mid+1, hi)
    
    // 如果左右两部分的多数元素相同，直接返回
    if left == right {
        return left
    }
    
    // 计算左右两部分多数元素在整个区间内的出现次数
    leftCount := countInRange(nums, left, lo, hi)
    rightCount := countInRange(nums, right, lo, hi)
    
    // 返回出现次数较多的元素
    if leftCount > rightCount {
        return left
    }
    return right
}

func countInRange(nums []int, num, lo, hi int) int {
    count := 0
    for i := lo; i <= hi; i++ {
        if nums[i] == num {
            count++
        }
    }
    return count
}

示例演示：对于复杂的分治算法，我们以一个简化的例子 [2,2,1,1,1,2,2] 展示部分步骤：

  1. 将数组分为两部分：[2,2,1] 和 [1,1,2,2]
  2. 递归地处理左半部分：进一步分为 [2] 和 [2,1]，最终得到左半部分的多数元素 2
  3. 递归地处理右半部分：进一步分为 [1,1] 和 [2,2]，最终得到右半部分的多数元素没有（因为 1 和 2 的出现次数相同）
  4. 比较左右两部分的多数元素在整个数组中的出现次数：2 出现了 4 次，1 出现了 3 次
  5. 返回 2 作为整个数组的多数元素

方法四：摩尔投票法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func majorityElement(nums []int) int {
    // 选第一个数字作为候选人
    candidate := nums[0]
  
    // 候选人的初始票数为1
    count := 1
  
    // 从第二个数字开始统计
    for i := 1; i < len(nums); i++ {
        // 如果当前票数为0，换新候选人
        if count == 0 {
            candidate = nums[i]
            count = 1
        } else if nums[i] == candidate {
            // 如果遇到和候选人一样的数字，票数+1
            count++
        } else {
            // 如果遇到和候选人不一样的数字，票数-1
            count--
        }
    }
  
    // 最后剩下的候选人就是多数元素
    return candidate
}

示例演示：让我们用数组 [2,2,1,1,1,2,2] 来一步步看看上面的算法是怎么工作的：

  1. 初始状态：
    • 候选人 = 2（第一个元素）
    • 票数 = 1
  2. 遍历第2个元素（也是2）：
    • 发现和候选人相同
    • 票数 +1 = 2
  3. 遍历第3个元素（是1）：
    • 发现和候选人不同
    • 票数 -1 = 1
  4. 遍历第4个元素（是1）：
    • 发现和候选人不同
    • 票数 -1 = 0
  5. 遍历第5个元素（是1）：
    • 票数为0，所以换新候选人
    • 候选人 = 1
    • 票数 = 1
  6. 遍历第6个元素（是2）：
    • 发现和候选人不同
    • 票数 -1 = 0
  7. 遍历第7个元素（是2）：
    • 票数为0，所以换新候选人
    • 候选人 = 2
    • 票数 = 1
  8. 遍历结束，最终候选人是2，这就是我们要的答案！

用表格表示更清晰：

当前位置 当前数字 候选人 票数 操作说明
开始 - 2 1 初始状态，选第一个数为候选人
位置1 2 2 2 遇到相同数字，票数+1
位置2 1 2 1 遇到不同数字，票数-1
位置3 1 2 0 遇到不同数字，票数-1
位置4 1 1 1 票数变为0，换新候选人
位置5 2 1 0 遇到不同数字，票数-1
位置6 2 2 1 票数变为0，换新候选人

为什么这个算法有效？

因为多数元素出现次数超过了数组长度的一半，所以即使它和其他所有元素一一"对抗"（相互抵消），最后剩下的也必定是它。

就像两支军队打仗：

  • 红军（多数元素）有100人
  • 蓝军（其他所有元素）合起来最多只有99人
  • 即使红蓝双方一对一厮杀，最终也会剩下至少1个红军

无论如何变换候选人，最终留下的一定是出现次数最多的那个元素。这就是摩尔投票算法的巧妙之处！

方法比较

方面 哈希表计数法 排序法 分治法 摩尔投票法
时间复杂度 O(n) O(n log n) O(n log n) O(n)
空间复杂度 O(n) O(1) 或 O(n) O(log n) O(1)
优点 直观易懂 实现简单 可以扩展到其他问题 最高效
缺点 需要额外空间 速度较慢 实现复杂 不直观
推荐度 ★★★★☆ ★★★☆☆ ★★★☆☆ ★★★★★

复杂度分析

哈希表计数法

  • 时间复杂度：$O(n)$，需要遍历数组两次
  • 空间复杂度：$O(n)$，最坏情况下哈希表需要存储 $n/2+1$ 个不同的元素

排序法

  • 时间复杂度：$O(n \log n)$，主要是排序的时间复杂度
  • 空间复杂度：$O(1)$ 或 $O(n)$，取决于使用的排序算法（原地排序或非原地排序）

分治法

  • 时间复杂度：$O(n \log n)$
    递归树的深度为 $\log n$，每层的总操作次数为 $O(n)$，因此总时间复杂度为 $O(n \log n)$
  • 空间复杂度：$O(\log n)$，递归调用栈的深度

摩尔投票法

  • 时间复杂度：$O(n)$，只需要遍历数组一次
  • 空间复杂度：$O(1)$，只使用了常数个变量

关键收获

  1. 多角度解决问题：同一个问题可以有多种解法，每种解法都有其优缺点

  2. 算法效率的权衡：

    • 哈希表方法直观但需要额外空间
    • 排序方法简单但效率不高
    • 分治法思想优雅但实现复杂
    • 摩尔投票法高效但不够直观

  3. 摩尔投票算法的巧妙之处：

    • 利用"不同元素相互抵消"的思想解决问题
    • 不需要额外空间，一次遍历即可得到结果
    • 是解决"多数元素"问题的最佳算法

  4. 问题的扩展思考：

    • 如果不保证存在多数元素，需要增加验证步骤
    • 可以扩展到寻找出现次数大于 n/3 的元素（LeetCode 229）
    • 可以用于解决其他计数相关的问题

相关题目

  • LeetCode 229: 求众数 II（找出所有出现次数超过 n/3 的元素）
  • LeetCode 1150: 检查一个数是否在数组中占绝大多数