*39. 数组中出现次数超过一半的数字【哈希/摩尔投票】

1. 问题

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

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

示例 1：

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制：

  • 1 <= 数组长度 <= 50000

2. 标签

  • 位运算

  • 分治

3. 解法 - 摩尔投票法

3.1 Java


// 摩尔投票法
// ref: https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/
class Solution {
    public int majorityElement(int[] nums) {
        // 众数（本题的众数定义为数组中出现次数超过一半的数，并不是传统意义的众数）
        int mode = 0;
        // 票数和
        int votes = 0;

        // 遍历所有数字
        for (int num : nums) {
            // 当票数和为 0 时，就假设当前数字是众数 mode
            // 所以是先假设第一个数组是众数
            if (votes == 0)
                mode = num;

            // 如果当前数字是众数，票数+1，反之票数-1
            if (num == mode)
                votes += 1;
            else
                votes -= 1;

        }

        return mode;
    }
}

3.2 Kotlin

class Solution {
    fun majorityElement(nums: IntArray): Int {
        // 众数
        var mode = 0
        // 票数和
        var votes = 0

        // 遍历所有数字
        for (num in nums) {
            // 当票数和为 0 时，就假设当前数字是众数 mode
            if (votes == 0)
                mode = num

            // 如果当前数字是众数，票数+1，反之票数-1
            if (num == mode)
                votes += 1
            else
                votes -= 1

        }

        return mode
    }
}

3.3 复杂度分析

  • 时间复杂度 O(N) ：N 为数组的长度。

  • 空间复杂度 O(1) ：变量仅仅使用常数大小的额外存储空间。

4. 参考

上一页38. 字符串的排列【DFS】下一页40. 最小的k个数【堆】

最后更新于

这有帮助吗？