169. 多数元素

力扣题目链接 (opens new window)

题目描述

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

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

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

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

提示：

• n == nums.length
• 1 <= n <= 5 * 10⁴
• -10⁹ <= nums[i] <= 10⁹

进阶： 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

思路

这道题有多种解法,我们从简单到高级逐个分析。

方法一:哈希表统计

很明显暴力的解法就是用哈希表统计每个元素出现的次数,然后找出现次数大于 n/2 的元素。

用 map 记录每个元素的出现次数,key 是元素值,value 是出现次数。遍历一遍数组就能找到答案。

时间复杂度 O(n),空间复杂度 O(n)。

方法二:排序

还有一个更简单的思路:如果将数组排序,那么出现次数大于 n/2 的元素一定会占据中间位置。

为什么呢?因为多数元素的出现次数超过一半,无论它分布在哪里,排序后必然会"霸占"中间的位置。

时间复杂度 O(n log n),空间复杂度 O(log n)(排序的递归栈)。

方法三:摩尔投票法(Boyer-Moore Voting Algorithm)

这是本题的最优解法,也是进阶要求的 O(n) 时间 O(1) 空间解法。

摩尔投票法的核心思想是:把数组看作多个阵营的对抗,不同的元素相互抵消,最后剩下的一定是多数元素。

具体做法:

1. 维护一个候选元素 candidate 和它的票数 count
2. 遍历数组:
   • 如果 count == 0,将当前元素设为候选元素
   • 如果当前元素等于候选元素,count++
   • 如果当前元素不等于候选元素,count--(抵消)
3. 遍历结束后,candidate 就是多数元素

为什么这个算法是正确的?

因为多数元素出现次数大于 n/2,即使所有其他元素联合起来抵消它,多数元素的票数也不会被完全抵消,最终一定会剩下。

时间复杂度 O(n),空间复杂度 O(1)。

模拟过程

以 nums = [2,2,1,1,1,2,2] 为例,演示摩尔投票法:

初始状态:

• candidate = 0
• count = 0

遍历过程:

当前元素	count == 0?	操作	candidate	count
2	是	设为候选	2	1
2	否	相同,count++	2	2
1	否	不同,count--	2	1
1	否	不同,count--	2	0
1	是	设为候选	1	1
2	否	不同,count--	1	0
2	是	设为候选	2	1

最终结果: candidate = 2,就是多数元素。

drawio 提示词: 画一个摩尔投票的抵消过程图。第一张展示数组 [2,2,1,1,1,2,2],用不同颜色标注 2 和 1,画出初始的"阵营"概念。第二张展示逐步抵消的过程,用天平或对抗的形式表现"相同+1,不同-1"的逻辑,最后 2 胜出。两张图画布统一,Logo 放左下角。

文件名:

• 0169.majority-element-01-camps.drawio
• 0169.majority-element-02-voting-process.drawio

解题代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0;
        int count = 0;
        
        for (int num : nums) {
            if (count == 0) {
                candidate = num; // count 为 0 时,更新候选元素
            }
            
            if (num == candidate) {
                count++; // 相同元素,票数+1
            } else {
                count--; // 不同元素,抵消,票数-1
            }
        }
        
        return candidate;
    }
};

复杂度分析

• 时间复杂度:O(n),只需遍历一遍数组
• 空间复杂度:O(1),只用了两个变量

其他语言

Python3

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = 0
        count = 0
        
        for num in nums:
            if count == 0:
                candidate = num
            
            count += (1 if num == candidate else -1)
        
        return candidate

Java

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            
            count += (num == candidate) ? 1 : -1;
        }
        
        return candidate;
    }
}

Go

func majorityElement(nums []int) int {
    candidate := 0
    count := 0
    
    for _, num := range nums {
        if count == 0 {
            candidate = num
        }
        
        if num == candidate {
            count++
        } else {
            count--
        }
    }
    
    return candidate
}

JavaScript

var majorityElement = function(nums) {
    let candidate = 0;
    let count = 0;
    
    for (const num of nums) {
        if (count === 0) {
            candidate = num;
        }
        
        count += (num === candidate ? 1 : -1);
    }
    
    return candidate;
};

与代码随想录联系

摩尔投票法是一个非常巧妙的算法,体现了"对抗抵消"的思想。

这种思维在算法题中很有用,当题目保证某个元素的数量占优时,就可以考虑用投票/抵消的方式找到它。

如果录友们想了解更多数组技巧,可以看代码随想录的数组章节,里面有很多经典的数组操作和优化技巧。

另外,本题也可以用哈希表解决,这在代码随想录哈希表章节有详细讲解,哈希表是统计元素出现次数的利器。