Easy

题目描述

给定一个大小为 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^4
  • -10^9 <= nums[i] <= 10^9
  • 输入保证数组中一定存在多数元素

进阶: 你能否用线性时间和 O(1) 空间复杂度来解决这个问题？

解题思路

本题有多种解法，从简单到高级：

方法一：哈希表统计 遍历数组，用哈希表记录每个元素的出现次数，当某个元素次数超过 n/2 时返回该元素。时间 O(n)，空间 O(n)。

方法二：排序 将数组排序后，位于索引 n/2 的元素必定是多数元素。因为多数元素出现次数超过一半，排序后必然占据中间位置。时间 O(n log n)，空间 O(1)。

方法三：Boyer-Moore 投票算法（推荐） 这是最优解法，满足线性时间和常数空间的要求。算法思想类似于"打擂台"：

  • 维护一个候选元素和计数器
  • 遍历数组，如果当前元素等于候选元素，计数器+1；否则计数器-1
  • 当计数器为0时，更新候选元素为当前元素，计数器重置为1
  • 由于多数元素出现次数超过一半，最终的候选元素必定是多数元素

这个算法的核心思想是：多数元素与其他所有元素"对抗"时，最后必然获胜。

代码实现

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = nums[0];
        int count = 1;
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == candidate) {
                count++;
            } else {
                count--;
                if (count == 0) {
                    candidate = nums[i];
                    count = 1;
                }
            }
        }
        
        return candidate;
    }
};

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

public class Solution {
    public int MajorityElement(int[] nums) {
        int candidate = nums[0];
        int count = 1;
        
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] == candidate) {
                count++;
            } else {
                count--;
                if (count == 0) {
                    candidate = nums[i];
                    count = 1;
                }
            }
        }
        
        return candidate;
    }
}

var majorityElement = function(nums) {
    let candidate = nums[0];
    let count = 1;
    
    for (let i = 1; i < nums.length; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型Boyer-Moore算法哈希表方法排序方法
时间复杂度O(n)O(n)O(n log n)
空间复杂度O(1)O(n)O(1)

相关题目