Leetcode刷题java之347. 前 K 个高频元素(一天一道编程题之第六天)

浅浅的花香味﹌ 2023-07-08 10:29 18阅读 0赞

执行结果：

通过

显示详情

执行用时 :22 ms, 在所有 Java 提交中击败了62.75% 的用户

内存消耗 :42.4 MB, 在所有 Java 提交中击败了7.20%的用户

题目：

给定一个非空的整数数组，返回其中出现频率前 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 是数组的大小。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/top-k-frequent-elements  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

利用堆来实现

参考：[https://leetcode-cn.com/problems/top-k-frequent-elements/solution/qian-k-ge-gao-pin-yuan-su-by-leetcode/][https_leetcode-cn.com_problems_top-k-frequent-elements_solution_qian-k-ge-gao-pin-yuan-su-by-leetcode]

值得注意的方法

getOrDefault（key，默认值）

keySet（）

Collections.reverse（）

代码：

class Solution {
        public List<Integer> topKFrequent(int[] nums, int k) {
            //构建一个map，key是值，value是该值出现的次数
            HashMap<Integer,Integer> hash=new HashMap<>();
            for(int num:nums)
            {
                hash.put(num,hash.getOrDefault(num,0)+1);
            }
            //构建一个优先队列，优先队列默认是最小堆
            //这里传入一个比较器的原因是我们入队的是key，但是比较的确是value
            PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>()
            {
                public int compare(Integer a,Integer b)
                {
                    return hash.get(a)-hash.get(b);
                }
            });
            //让堆里始终有k个元素
            for(int key:hash.keySet())
            {
                queue.add(key);
                if(queue.size()>k)
                {
                    queue.poll();
                }
            }
            //将结果放到rlist中
            List<Integer> result=new ArrayList<>();
            while(!queue.isEmpty())
            {
                result.add(queue.poll());
            }
            //反转
            Collections.reverse(result);
            return result;
        }
    }

[https_leetcode-cn.com_problems_top-k-frequent-elements_solution_qian-k-ge-gao-pin-yuan-su-by-leetcode]: https://leetcode-cn.com/problems/top-k-frequent-elements/solution/qian-k-ge-gao-pin-yuan-su-by-leetcode/