LeetCode no.347 Solution

一、题目简介及问题分析

本文首发于心安-XinAnzzZ 的个人博客，转载请注明出处~

问题描述

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

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n36" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> 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);
}
}
}
}</pre>

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n38" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> 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);
}
}
}</pre>

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n41" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> 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();
}
}
}</pre>

<pre spellcheck="false" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" lang="java" cid="n43" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Monaco, Consolas, "Andale Mono", "DejaVu Sans Mono", monospace; margin-top: 0px; margin-bottom: 20px; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: inherit; font-size: 0.9rem; display: block; break-inside: avoid; text-align: left; white-space: normal; position: relative !important; padding: 10px 30px 10px 0px; border: 1px solid; width: inherit; background-position: inherit inherit; background-repeat: inherit inherit;"> 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);
}
}</pre>

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

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

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

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

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

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

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

二、使用自定义优先队列

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

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

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

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

问题分析

说明：

你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。

你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

示例 2:

最后编辑于：2019.05.16 09:47:26

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,324评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,303评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,192评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,555评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,569评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,566评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,927评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,583评论 0赞 257
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,827评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,590评论 2赞 320
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,669评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,365评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,941评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,928评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,159评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,880评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,399评论 2赞 342

LeetCode no.347 Solution

一、题目简介及问题分析

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

二、使用自定义优先队列

推荐阅读更多精彩内容