这道题主要涉及的是对数据结构里哈希表、小顶堆的理解,优化时可以参考一些排序方法。
原题
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例 1:
<code>输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
/<code>
示例 2:
<code>输入: nums = [1], k = 1
输出: [1]
/<code>
说明:
- 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
原题url:
https://leetcode-cn.com/problems/top-k-frequent-elements/
解题
正常思路
为了解决这道题,我们首先需要知道每个元素出现的次数。最方便的话,可以使用哈希表,因为这就是一个数字——出现次数的映射关系。此处的时间复杂度为O(n)
其次,因为需要查找频率前 k 高的元素,所以我们肯定是需要排序的,时间复杂度为O(n log n)的排序方法有许多,快速排序、堆排序等,我是用的堆排序,使用小顶堆,这样在每次入堆的时候,检查一下堆的个数是否超过 k,如果超过,则移除堆顶的元素(也就是次数最少的元素)。
这样堆里剩余的元素也就是最终的结果了,接下来我们看看代码:
<code>class
Solution
{public
ListtopKFrequent
(int
[] nums,int
k) { Map countMap =new
HashMap<>();for
(int
num : nums) { countMap.put(num, countMap.getOrDefault(num,0
) +1
); } PriorityQueue heap =new
PriorityQueue((n1, n2) -> countMap.get
(n1) - countMap.get
(n2)); Set keySet = countMap.keySet();for
(int
key : keySet) { heap.add
(key);if
(heap.size() > k) { heap.poll(); } } List result =new
LinkedList<>(); Iterator iterator = heap.iterator();while
(iterator.hasNext()) { result.add
(iterator.next()); }return
result; } }/<code>
提交OK。
桶排序优化
针对排序,我想到了一个优化,利用桶排序,其时间复杂度为O(n),主要是浪费空间,因为需要申请额外的数组,下标代表出现的次数,元素我用的是 LinkedList,这样可以存储多个。那么这个在进行输出时,只要从后往前进行遍历,当结果的数量达到 k 时,就可以停止了。
接下来我们看看代码 :
<code>class
Solution
{public
List topKFrequent(int
[] nums,int
k) { Map countMap =new
HashMap<>();int
maxCount =0
;for
(int
num : nums) {int
count = countMap.getOrDefault(num,0
) +1
;if
(count > maxCount) { maxCount = count; } countMap.put(num, count); } LinkedList[]array
=new
LinkedList[maxCount +1
];for
(Map.Entry entry : countMap.entrySet()) {int
key = entry.getKey();int
count = entry.getValue(); LinkedListlist
=array
[count];if
(list
== null) {list
=new
LinkedList<>();array
[count] =list
; }list
.add(key); } List result =new
LinkedList<>();for
(int
i =array
.length -1
; i >=0
&& result.size() < k; i--) { Listlist
=array
[i];if
(list
== null) {continue
; } result.addAll(list
); }return
result; } }/<code>
提交OK。
总结
以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题主要涉及的是对数据结构的理解,优化时可以参考一些特殊的排序方法。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。
https://death00.github.io/
關鍵字: LinkedList nums 元素