LeetCode #169 多数元素

Problem Description

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

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

e.g.

• 示例 1:
  • 输入: [3,2,3]
  • 输出: 3
• 示例 2:
  • 输入: [2,2,1,1,1,2,2]
  • 输出: 2

Solution

Hash 表

首先最容易想到的，利用 Hash 表：

public static int majorityElement(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>(nums.length / 3 * 4 + 1);
    int max = nums.length / 2;
    AtomicInteger result = new AtomicInteger();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    map.forEach((k, v) -> {
        if (v > max) {
            result.set(k);
        }
    });
    return result.get();
}

key 来保存数组的元素，value 来保存出现的次数。

因为众数的个数一定是大于 n/2 的，所以只要取出 value 大于 n/2 的 key 即可。

随机流&暴力流

public static int thirdMethod(int[] nums) {
		int count = 0;
    int index = (int) (Math.random() * nums.length);
    int fuck = nums[index];
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == fuck) {
            count++;
        }
        if (count > nums.length / 2) {
            return nums[index];
        } else if (i == (nums.length - 1)) {
            count = 0;
            i = -1;
            index = (int) (Math.random() * nums.length);
            fuck = nums[index];
        }
    }
    return 0;
}

众数在题干中明确说明了个数是 n/2，一定是占据一半以上的，所以随机抽取一个元素，较大可能性是众数。统计该元素的个数，符合个数大于 n/2 即可。一开始设置第一个元素为众数统计个数，全部遍历后如果不符合，则设置第二个元素为基准继续遍历。这样其实就和双 for 循环没什么区别了，不具随机性。

我一开始做法就是设置第一个元素为基准，这样写的最大时间复杂度是平方级 O(n²)，一旦众数全部位于数组的后半段，那么时间会超久，所以我这样提交，系统判定超出时间限制。

官方题解是随机设置一个基准，理想情况是众数较多，很容易抽中，较少的次数可以完成推断，但是存在一种极限情况，就是每次随机基准都抽不到众数，那么会变成无穷尽的计算。最坏情况的时间复杂度为 O(∞)。

排序流

public static int secondMethod(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length / 2];
}

充分利用了 n/2 的特性，将数组排序后，无论数组的长度是奇数还是偶数，第 nums.length 一定是众数。

投票流

该方法个人认为最有意思和最有拓展性。假设这样一个数组：

[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]

1. 初始化被选举人（elector）为第一个数，设定 count = 1，然后开始遍历；
2. 当 nextValue == elector，count + 1，反之 - 1；
3. 当 count == 0 时，且存在 nextValue 时，nextValue 成为下一个 elector，count = 1；
4. 最终的选举人一定是那个众数

因为众数的个数一定是大于其它数字的和，所以相减一定大于 0，最后剩下的被投票的那个元素一定是众数。

所以上述的数组，票数就是 [1, 2, 1, 2, 1, 0 | 1, 0 | 1, 2, 1, 0 | 1, 2, 3, 4

遍历到数组的最后阶段，elector 是 7，后面票数越来越多，也不会被更换 elector 了。即使是众数都在前面

[7, 7, 7, 7, 7, 1, 5, 5 ]，众数的和也够减去后半段的其他元素的总和而保证 elector 不被更换。

该思想不复杂实现起来非常简单：

public static int boyerMoore(int[] nums) {
    int count = 1;
    int elector = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == elector) {
            count++;
        } else {
            count--;
        }
      	/*
         * 上面的if-else可以改成这样
         * count += (nums[i] == elector) ? 1 : -1;
         */
        if (i + 1 < nums.length && count == 0) {
            elector = nums[i + 1];
        }
    }
    return elector;
}