原题
给定一个非空的整数数组，返回其中出现频率前 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/
相关推荐
-
leetcode73-矩阵置零
原题 给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1: 输入: [ [1,1,1], ...
-
剑指offer45-把数组排成最小的数
原题（来源Leetcode） 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: "102" ...
-
leetcode705-设计哈希集合
原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说，你的设计应该包含以下的功能 add(value)：向哈希集合中插入一个值。 contains(value) ：返回哈希集合...
-
leetcode131-分割回文串
原题 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 返回 s 所有可能的分割方案。 示例: 输入: "aab" 输出: [ ["aa","b"], ...
-
leetcode1014-最佳观光组合
原题 给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。 一对景点（i < j）组成的观光组合的得分为（A[i]...
-
leetcode76-最小覆盖子串
原题 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。 示例: 输入: S = "ADOBECODEBANC", T = "ABC" 输...
-
leetcode887-鸡蛋掉落
原题 你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。 每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。 你知道存在楼层 F ，满足 0 &...
-
蓝桥杯试题-大小写转换
原题 资源限制 时间限制：1.0s 内存限制：256.0MB 问题描述 输入一个字符串，将大写字符变成小写、小写变成大写，然后输出 输入格式 acbAB 输出格式 ACBab ...
-
leetcode189-旋转数组
原题 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。 示例1: 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4...
-
leetcode56-合并区间
原题 给出一个区间的集合，请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]]...