LeetCode 剑指 Offer 39. 数组中出现次数超过一半的数字

Categories:

Tags:

题目描述
思路分析
1. 解法一：Boyer-Moore 投票算法（推荐）
2. 解法二：哈希表计数
相似题目

题目描述

✅ 剑指 Offer 39. 数组中出现次数超过一半的数字

思路分析

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

核心思路：

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

维护一个候选数 candidate 和计数器 count：遇到相同元素则 count++，遇到不同元素则 count--。

当 count 降为 0 时，说明当前候选数已被”抵消”，将下一个元素作为新的候选数，并重置 count = 1。

由于多数元素出现次数超过半数，最终留下的候选数必然是多数元素。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组的长度，只需一次遍历。

空间复杂度：O(1)，只使用了常数个额外变量。

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int 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，立即返回该元素。

该方法思路直观，但需要额外的哈希表空间。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组的长度，遍历一次数组。

空间复杂度：O(n)，哈希表最多存储 n 个键值对。

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> count = new HashMap<>();

        for (int num : nums) {
            // 累加当前元素计数
            count.merge(num, 1, Integer::sum);
            // 超过半数则直接返回
            if (count.get(num) > n / 2) {
                return num;
            }
        }

        return -1;
    }
}

func majorityElement(nums []int) int {
    n := len(nums)
    count := make(map[int]int)

    for _, num := range nums {
        // 累加当前元素计数
        count[num]++
        // 超过半数则直接返回
        if count[num] > n/2 {
            return num
        }
    }

    return -1
}

相似题目

题目	难度	考察点
169. 多数元素	简单	摩尔投票法
229. 求众数 II	中等	摩尔投票法
1150. 检查一个数是否在数组中占绝大多数	简单	二分查找
2780. 合法分割的最小下标	中等	摩尔投票法
347. 前 K 个高频元素	中等	堆、哈希表
136. 只出现一次的数字	简单	位运算
137. 只出现一次的数字 II	中等	位运算
448. 找到所有数组中消失的数字	简单	哈希表
215. 数组中的第K个最大元素	中等	快速选择

本文作者: HGNULB

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