剑指offer60：出现频率最高的k个数字

81 阅读 0 评论 54 点赞

我是靠谱客的博主甜美河马，最近开发中收集的这篇文章主要介绍剑指offer60：出现频率最高的k个数字，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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

2.输入: nums = [1], k = 1
输出: [1]
分析：
具体分析注释写的很详细，看代码注释即可，哈希表是用来统计数字出现的频率，它的键是数组中的数字，值是数字在数组中出现的次数，最小堆minHeap中的每个元素是哈希表从数字到频率的映射，因为最小堆比较的是数字的频率，因此调用构造函数创建minHeap设置的比较规则是比较哈希表中映射的值也就是数字的频率。代码需要空间复杂度O（n）的哈希表，O（k）的最小堆，在大小为k的堆中进行添加或删除操作的时间复杂度是O（logk），因此代码时间复杂度为O（nlogk）。
代码：

import java.util.*;

public class TopKFrequent {
    public static void main(String[] args) {
        int[] nums = {1,2,2,1,3,1};
        List<Integer> integers = topKFrequent(nums, 2);
        System.out.println(integers);
    }
    public static List<Integer> topKFrequent(int[] nums,int k){
        Map<Integer,Integer> numToCount = new HashMap<>();
        for (int num : nums) {
        //逐个给哈希表赋值
            numToCount.put(num,numToCount.getOrDefault(num,0)+1);
        }
        PriorityQueue<Map.Entry<Integer,Integer>> minHeap = new PriorityQueue<>(
        //参数是Comparator，因此lambda返回值如果是正数则代表大于，0代表相等，负数代表小于，（e1，e2）代表连续增加参数，比较参数
        //的大小
                (e1,e2) ->e1.getValue() - e2.getValue()
                );
                //遍历每个键值对
        for (Map.Entry<Integer,Integer> entry:numToCount.entrySet()){
        //如果小根堆的元素个数小于k，那么直接在小根堆添加键值对
            if (minHeap.size() <k) {
                minHeap.offer(entry);
            }else{
            //如果小根堆元素个数大于等于k，那么就比较键值对的值和小根堆的堆顶元素的值大小，如果大于堆顶元素的值则删除堆顶元素再入堆当前键值对
                if (entry.getValue() > minHeap.peek().getValue()){
                    minHeap.poll();
                    minHeap.offer(entry);
                }
            }
        }
        List<Integer> result = new LinkedList<>();
        //保存堆中每个元素键值对的键到一个列表中，因为java中列表中的元素不重复
        for (Map.Entry<Integer,Integer> entry: minHeap){
            result.add(entry.getKey());
        }
        return result;
    }
}