原题
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
示例1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例2:
输入: nums = [1], k = 1
输出: [1]
说明:
- 你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
解法
思想
可以用哈希表记录下出现的次数,然后将哈希表按值排序。(获取entryList用Collections来排序)
代码
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
List<Integer> list = new ArrayList<>();
for(int i:nums){
map.put(i,map.getOrDefault(i,0)+1);
}
List<Map.Entry<Integer,Integer>> entryList = new ArrayList<>(map.entrySet());
entryList.sort((entry1, entry2) -> entry2.getValue() - entry1.getValue());
int n = 0;
for(Map.Entry<Integer,Integer> i:entryList){
if(n>=k) break;
list.add(i.getKey());
n ++;
}
return list;
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode347-%e5%89%8dk%e4%b8%aa%e9%ab%98%e9%a2%91%e5%85%83%e7%b4%a0/