​LeetCode刷题实战347:前 K 个高频元素

程序IT圈

共 4267字,需浏览 9分钟

 ·

2021-08-09 20:35

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 前 K 个高频元素,我们先来看题面:
https://leetcode-cn.com/problems/top-k-frequent-elements/

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例


示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]


解题

https://www.cnblogs.com/qionglouyuyu/p/13430581.html

你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案。

思路:时间复杂度 O(n log n) -> 堆排序

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        //将每个数字的出现次数放入HashMap
        Map<Integer, Integer> counts = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(counts.containsKey(nums[i])){
                counts.put(nums[i], counts.get(nums[i])+1);
            } else {
                counts.put(nums[i], 1);
            }
        }

        //建立只有k个元素的最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare (Integer a, Integer b)
{
                //要重写compare函数:最小堆中存的是数字,但比较的是数字出现的频率。默认是大顶堆。
                return counts.get(a) - counts.get(b);
            }
        });
        for(Integer key: counts.keySet()){
            if(minHeap.size() < k) {
                minHeap.add(key);
            } else {
                if(counts.get(key) > counts.get(minHeap.peek())){
                    minHeap.remove();
                    minHeap.add(key);
                }
            }
        }

        //输出结果
        int[] result = new int[k];
        for(int i = 0; i < result.length; i++){
            result[i] = minHeap.remove();
        }
        return result;
    }
}


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-340题汇总,希望对你有点帮助!
LeetCode刷题实战341:扁平化嵌套列表迭代器
LeetCode刷题实战342:4的幂
LeetCode刷题实战343:整数拆分
LeetCode刷题实战344:反转字符串
LeetCode刷题实战345:反转字符串中的元音字母
LeetCode刷题实战346:数据流中的移动平均值

浏览 18
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报