leetcode347-前K个高频元素

原题

给定一个非空的整数数组,返回其中出现频率前 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/

发表评论

电子邮件地址不会被公开。