Toc
  1. Problem Description
    1. e.g.
  2. Solution
    1. Hash表
    2. 随机流&暴力流
    3. 排序流
    4. 投票流
Toc
0 results found
Espada
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 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(n2),一旦众数全部位于数组的后半段,那么时间会超久,所以我这样提交,系统判定超出时间限制。

官方题解是随机设置一个基准,理想情况是众数较多,很容易抽中,较少的次数可以完成推断,但是存在一种极限情况,就是每次随机基准都抽不到众数,那么会变成无穷尽的计算。最坏情况的时间复杂度为 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;
}
龙鸣
"老罗"
本文作者:Espada
版权声明:本文首发于Espada的博客,转载请注明出处!