leetcode169:多数元素

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

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

示例 1:

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

示例 2:

1
2
输入: [2,2,1,1,1,2,2]
输出: 2

题解

暴力

这直接分组得到数组内每个数值对应的count数值,过滤得出。

1
2
3
4
5
6
7
8
9
class Solution {
public int majorityElement(int[] nums) {
int count = nums.length / 2;
List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
Map<Integer, List<Integer>> collect = list.stream().collect(Collectors.groupingBy(Integer::intValue));
List<Integer> retList = collect.keySet().stream().filter(key -> collect.get(key).size() > count).collect(Collectors.toList());
return retList == null || retList.isEmpty() ? 0 : retList.get(0);
}
}

遗憾的是,效率忒低了,当我吧这条记录提交后,显示:

1
2
3
执行用时 :32 ms, 在所有 Java 提交中击败了9.90%的用户

内存消耗 :44.2 MB, 在所有 Java 提交中击败了5.07%的用户

难受啊,一下子感觉自尊心受到了一点点侮辱,两个百分比都没过两位数,当然通过题库官方解读,还是可以写出来剩下的几种方法和理解。

排序算法实现

如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序,那么下标为⌊\frac{n}{2} ⌋ 的元素(下标从 0 开始)一定是众数。

1
2
3
4
public static int majorityElement1(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}

复杂度分析

  • 时间复杂度:O(nlogn)。将数组排序的时间复杂度为 O(nlogn)
  • 空间复杂度:O(logn)。如果使用语言自带的排序算法,需要使用 O(logn) 的栈空间。如果自己编写堆排序,则只需要使用 O(1)O(1) 的额外空间。
  • hash实现

出现次数最多的元素大于 ⌊$\frac{n}{2}$⌋ 次,所以可以用哈希表来快速统计每个元素出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int majorityElement3(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
Integer count = map.get(num);
map.put(num, count == null ? 1 : ++count);
}

Map.Entry<Integer, Integer> majEntry = null;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (majEntry == null || entry.getValue() > majEntry.getValue()) {
majEntry = entry;
}
}
return majEntry.getKey();
}

复杂度分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

投票算法

如果把众数记为 +1,把其他数记为−1,将它们全部加起来,显然和大于0,从结果本身可以看出众数比其他数多。

可能不太好理解,点击此处带你飞

1
2
3
4
5
6
7
8
9
10
11
public static int majorityElement2(int[] nums) {
int maj = nums[0];
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (count == 0) {
maj = nums[i];
}
count += (maj == nums[i]) ? 1 : -1;
}
return maj;
}

复杂度分析

  • 时间复杂度:O(n)。Boyer-Moore 算法只对数组进行了一次遍历。
  • 空间复杂度:O(1)。Boyer-Moore 算法只需要常数级别的额外空间。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×