心安

LeetCode no.347 Solution

字数统计: 2.3k阅读时长: 9 min
2019/01/19 Share

一、题目简介及问题分析

原题链接:中文版英文版

  • 问题描述

给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

示例 1:

1
2
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

1
2
输入: nums = [1], k = 1
输出: [1]

说明:

  • 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
  • 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
  • 问题分析

题目让我们找出出现频率前 k 高的元素,最容易想到的解决思路应该是:

  1. 首先进行所有元素进行频率的统计。
  2. 然后对频率进行由大到小排序。
  3. 取出前 k 高的频率值所对应的元素。

频率的统计进行一次遍历就可以完成,那么这个题目可以归纳为在N个元素中取出前M个元素的问题,也就是经典的TOP N问题
在最后的说明中明确指出了算法的时间复杂度必须优于 O(n log n) ,但是我们知道就算是快速排序它的时间复杂度也是O(n log n)的,所以这个解决方法是不行的。

那么联系到我们之前所接触过的优先队列,如果我们用一个长度为M的优先队列来维护这M个元素,首先将这N个元素中的前M个元素放入到队列中,然后后面的元素和队列中的进行比较。
如果这个元素比队列中最小的元素还大,那么我们就将最小的元素出队,将这个元素入队,最后队列中剩下的就是这N个元素中前M大元素。
这样我们所需要的时间复杂度就是N(logM)。下面我们就分别使用我们自己写的优先队列以及JAVA为我们提供的优先队列来解决这个问题。

二、使用自定义优先队列

这里我们使用我们之前自己写的优先队列来尝试解决这个问题。
上面我们说到我们需要一个如果这个元素比队列中最小的元素还大,那么我们就将最小的元素出队,这也就意味着我们需要一个最小堆来保存这些元素。
但是我们之前的优先队列使用的是一个最大堆,当然我们可以对代码稍加改动让其变成一个最小堆,这是不是意味着最大堆就不行呢?并不是这样的,因为优先原则是可以由我们来定义的。
如果不太明白,结合代码就会好理解很多。

首先,建立名为Solution的类,并且使用Map集合来完成频率的统计,其中key表示元素,value表示出现的频率:

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new TreeMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
}
}

然后建立内部类Frequent,成员变量e、frequency分别表示元素及其出现的频率,每一个Frequent对象就是一个Map.Entry对象,不同的是我们可以让这个对象具有可比较性。
这个类实现了Comparable接口,重写了compareTo方法,比较的规则是如果当前元素的频率小于新传入的元素返回1,也就是返回当前元素大于传入的元素。
这其实就是改变了它的比较性,试想一下,当队列中装了M个元素的时候,队首的元素应该就是“最大的元素”,而由于我们改变了Frequent对象的比较性,Frequent对象的频率越小,这个对象就越大,所以队首的元素就是队列中频率最小的Frequent对象。
那么当新来的Frequent对象的频率值比队首的Frequent对象的频率值大的时候,就将队首的元素出队,将Frequent对象入队,然后队列中又自动将频率最小的元素换到队首的位置。
这样一来,新来的对象始终都是和队列中频率最小的Frequent对象进行比较,并且每次都是把频率最小的Frequent对象出队,那么当遍历完成,队列中留下的就是频率前M大的Frequent对象了。
下面是全部的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new TreeMap<>();
// 首先遍历数组,进行频率的统计,将统计结果放入map中。
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}

// 这个set中每一个entry就是一个元素及其出现的频率值,也就对应了一个Frequent对象
Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
PriorityQueue<Frequent> queue = new PriorityQueue<>();
for (Map.Entry<Integer, Integer> entry : entries) {
// 如果队列里面的元素小于K就直接入队
if (queue.size() < k) {
queue.enqueue(new Frequent(entry));
}else {
// 如果队首的Frequent对象的频率小于新来的Frequent对象的频率,就将队首的元素出队,新元素入队
if (queue.getFront().frequency < entry.getValue()) {
queue.dequeue();
queue.enqueue(new Frequent(entry));
}
}
}
// 遍历完成之后,队列中剩余的元素就是这所有元素中频率前k大的元素了。

LinkedList<Integer> list = new LinkedList<>();
// 将这前k大的元素放进list并且返回
while (!queue.isEmpty()) {
list.add(queue.dequeue().e);
}

return list;
}

private class Frequent implements Comparable<Frequent>{
int e, frequency;

Frequent(Map.Entry<Integer, Integer> entry) {
this.e = entry.getKey();
this.frequency = entry.getValue();
}

@Override
public int compareTo(Frequent another) {
if (this.frequency < another.frequency) {
return 1;
} else if (this.frequency > another.frequency) {
return -1;
} else {
return 0;
}
// 上面的代码可以简写为下面这一行代码
// return Integer.compare(another.frequency, this.frequency);
}
}
}

三、使用JAVA为我们提供的优先队列

java.util包为我们提供了一个名为PriorityQueue的优先队列,它底层是使用一个最小堆来实现的。
上面我们使用的优先队列底层是最大堆实现的,所以如果使用Java为我们提供的队列的话,只需要修改Frequent对象的比较性即可,代码示例和上面大同小异,这里就不再贴具体代码了。
这里我们主要要做的是不再让Frequent对象具有可比较性,而是传入一个自定义的比较器java.util.Comparator
这一点不太明白的同学可以回想一下在你学习java.util.TreeSet这个集合的时候,就要求所装的对象必须具有可比较性或者在实例化这个集合的时候传入一个java.util.Comparator比较器对象。
下面我们看一下代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new TreeMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}

Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
java.util.PriorityQueue<Frequent> queue = new java.util.PriorityQueue<>(new Comparator<Frequent>() {
@Override
public int compare(Frequent o1, Frequent o2) {
return o1.frequency - o2.frequency;
}
});

for (Map.Entry<Integer, Integer> entry : entries) {
if (queue.size() < k) {
queue.add(new Frequent(entry));
} else if (queue.peek().frequency < entry.getValue()) {
queue.remove();
queue.add(new Frequent(entry));
}
}

LinkedList<Integer> list = new LinkedList<>();
while (!queue.isEmpty()) {
list.add(queue.remove().e);
}

return list;
}

private class Frequent {
int e, frequency;

Frequent(Map.Entry<Integer, Integer> entry) {
this.e = entry.getKey();
this.frequency = entry.getValue();
}
}
}

上面的代码传入的比较器是以匿名内部类的方式实现的,而在Java中,匿名内部类有一个特性就是可以访问所在方法中被final修饰的变量
同样的,在匿名内部类中也可以访问集合中的数据,再使用Java8的新特性,我们的代码将能够改写为下面这个样子,大大的减少了我们的代码量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new TreeMap<>();
for (int num : nums) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}

/*
下面的代码可以简写为下面一行代码
java.util.PriorityQueue<Integer> queue = new java.util.PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return map.get(o1) - map.get(o2);
}
});
这一行代码还可以继续简化为下面这行代码
java.util.PriorityQueue<Integer> queue = new java.util.PriorityQueue<>((o1, o2) -> map.get(o1) - map.get(o2));
*/
java.util.PriorityQueue<Integer> queue = new java.util.PriorityQueue<>(Comparator.comparingInt(map::get));
for (int key : map.keySet()) {
if (queue.size() < k) {
queue.add(key);
} else if (map.get(queue.peek()) < map.get(key)) {
queue.remove();
queue.add(key);
}
}

return new ArrayList<>(queue);
}
}

示例代码Github

以上就是博主为各位看官带来的LeetCode no.347题目的解决思路,如果各位看官有其他更好解决思路,也欢迎在评论区进行讨论,感谢阅读。

原文作者:XinAnzzZ

原文链接:https://www.yuhangma.com/2019/algorithm/2019-01-19-leetcode-solution-347/

发表日期:January 19th 2019, 12:00:00 am

更新日期:September 26th 2019, 10:46:42 am

版权声明:(转载本站文章请注明作者和出处 心 安 – XinAnzzZ ,请勿用于任何商业用途)

CATALOG
  1. 1. 一、题目简介及问题分析
  2. 2. 二、使用自定义优先队列
  3. 3. 三、使用JAVA为我们提供的优先队列