找出数组中的多数元素

,

今天做到一道题，题很简单，但是其中一些解法非常有意思，算法思想可以学习。

题目描述

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

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

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

解析 1（Boyer-Moore 投票算法）

本题的普通解法很简单，可以用 HashMap 记录出现次数，这样做时间复杂度是 O(n)，空间复杂度是 O(n)；也可以直接排序，返回数组的下标为 n/2 的数即可，时间复杂度为 O(nlogn)，空间复杂度是 O(1)。

但这题还有一种解法非常有意思，叫 Boyer-Moore 投票算法，也叫摩尔投票算法。这一算法应用的问题原型是在集合中寻找可能存在的多数元素，这一元素在输入的序列重复出现并占到了序列元素的一半以上。

算法有 计数器 与 当前多数元素

  • 计数器 初始为 0
  • 对数组进行遍历，当碰到元素 x 时，如果 计数器 为 0，则将当前元素 x 赋值给 当前多数元素，并判断当前 当前多数元素 与元素 x 是否相等，如果相等 计数器+1，否则-1。
  • 这个过程结束后，最终的 当前多数元素 即是数组中的多数元素。

此外，还可以二次遍历，来确定此多数元素的次数，本题无此需要。

参考 1

1
2
3
4
5
6
7
8
9
10
11
public int majorityElement(int[] nums) {
    int count = 0;
    int candidate = 0;
    
    for(int num : nums){
        if(count == 0) candidate = num;

        count += (num == candidate) ? 1 : -1;
    }
    return candidate;
}

时间复杂度： O(n)

空间复杂度： O(1)

解析 2（随机化）

还有另一种解法也很有意思，因为是寻找数组中的多数元素，所以可以去随机寻找数组任意下标的数，并验证其出是否是多数元素，如果不是，则重复以上步骤，直到找出多数元素。因为寻找的是多数元素，所以随机找到的概率很大。

参考 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int majorityElement(int[] nums) {
    Random random = new Random();

    int target = nums.length / 2;

    while (true){
        int candidate = random.nextInt(nums.length);
        int count = 0;
        
        for(int num : nums){
            if(num == candidate) count++;
        }
        if(count >= target) return candidate;
    }
}

时间复杂度： O(n)，在最坏的情况下，时间复杂度为 O(∞)，这取决于所谓的“运气”。但由于寻找的是多数元素，寻找的期望次数为 2，因此时间复杂度是 O(n)。

空间复杂度： O(1)

相关链接

169. 多数元素 - 力扣（LeetCode）

Boyer–Moore majority vote algorithm - Wikipedia

yzlzzzdeveloper