原题
给定一个非空的整数数组，返回其中出现频率前 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/
相关推荐
-
leetcode221-最大正方形
原题 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 ...
-
leetcode373-查找和最小的K对数字
原题 给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。 定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。 找到和最...
-
leetcode59-螺旋矩阵II
原题 给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, ...
-
leetcode706-设计哈希映射
原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说，你的设计应该包含以下的功能 put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更...
-
leetcode387-字符串中的第一个唯一字符
原题 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。 案例: s = "leetcode" 返回 0. s = "loveleetcode"...
-
leetcode374-猜数字大小
原题 我们正在玩一个猜数字游戏。 游戏规则如下：我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。每次你猜错了，我会告诉你这个数字是大了还是小了。你调用一个预先定义好的接...
-
leetcode704-二分查找
原题 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 示...
-
leetcode739-每日温度
原题 根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 te...
-
一致性哈希算法的介绍
本文参考资源： 一致性Hash算法详解 - 知乎 一致性哈希算法概述 分布式系统中，常常听到一种算法叫一致性哈希算法，而最常用的领域相信大家也有所耳闻——负载均衡。负载均衡有许多算...
-
leetcode111-二叉树的最小深度
原题 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,nul...
