LeetCode 169. 多数元素

Categories:

Tags:

题目描述
思路分析
1. 解法一：Boyer-Moore 投票算法（推荐）
2. 解法二：排序取中值
相似题目

题目描述

✅ 169. 多数元素

思路分析

解法一：Boyer-Moore 投票算法（推荐）

核心思路：

多数元素出现次数严格大于 n/2，意味着它比所有其他元素加起来还多。

维护一个候选人 candidate 和净票数 count，初始 count = 0。

遍历每个元素：若 count == 0 则更换候选人；否则遇到相同元素 count++，遇到不同元素 count--（两票相抵）。

将不同元素两两相消后，多数元素数量超过一半，相消后一定有剩余，最终留下的候选人即为多数元素。

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，只需一次线性遍历。

空间复杂度：O(1)，只使用常数级额外空间存储候选人和计数器。

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0, count = 0;
        for (int num : nums) {
            // 票数归零时更换候选人
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                // 与候选人相同，票数加一
                count++;
            } else {
                // 与候选人不同，两票相抵
                count--;
            }
        }
        return candidate;
    }
}

func majorityElement(nums []int) int {
    candidate, count := 0, 0

    for _, num := range nums {
        // 票数归零时更换候选人
        if count == 0 {
            candidate = num
            count = 1
        } else if num == candidate {
            // 与候选人相同，票数加一
            count++
        } else {
            // 与候选人不同，两票相抵
            count--
        }
    }
    return candidate
}

解法二：排序取中值

核心思路：

将数组排序后，多数元素（出现次数 > n/2）一定占据中间位置 n/2，直接返回 nums[n/2] 即可。

无需额外统计，排序后中间元素必然是多数元素。

复杂度分析：

时间复杂度：O(n log n)，其中 n 为数组长度，瓶颈在排序。

空间复杂度：O(log n)，排序递归栈空间（Java/Go 内置排序）。

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        // 多数元素必然占据中间位置
        return nums[nums.length / 2];
    }
}

import "sort"

func majorityElement(nums []int) int {
    sort.Ints(nums)
    // 多数元素必然占据中间位置
    return nums[len(nums)/2]
}

相似题目

题目	难度	考察点
229. 多数元素 II	中等	摩尔投票（维护两个候选人）
1150. 检查一个数是否在数组中占绝大多数	简单	二分查找
2780. 合法分割的最小下标	中等	摩尔投票 + 前缀计数
1157. 子数组中占绝大多数的元素	困难	摩尔投票 + 线段树
137. 只出现一次的数字 II	中等	位运算 / 摩尔投票变种

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/37922469