LeetCode——剑指 Offer II 060. 出现频率最高的 k 个数字题目思路代码结果

106 阅读 0 评论 70 点赞

我是靠谱客的博主机灵夕阳，这篇文章主要介绍LeetCode——剑指 Offer II 060. 出现频率最高的 k 个数字题目思路代码结果，现在分享给大家，希望可以做个参考。

出现频率最高的 k 个数字

题目
思路
代码
结果

题目

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

思路

先利用一个hashmap来统计各个数字的个数，然后，将这个哈希表转化为一个优先队列，根据计数数字的大小来作为优先级判断。最终，优先队列的前k个元素就是所要寻找的答案！

代码

复制代码

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.TreeMap;
// 自定义元素
class Element
{
    int num;
    int count;
    public Element(int num,int count)
    {
        this.num=num;
        this.count=count;
    }

@Override
    public String toString() {
        return "Element{" +
                "num=" + num +
                ", count=" + count +
                '}';
    }
}
// 自定义排序规则
class  MyCmp implements Comparator<Element>
{
    @Override
    public int compare(Element o1, Element o2) {
        return o2.count-o1.count;
    }
}
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        PriorityQueue<Element> priorityQueue = new PriorityQueue<>(new MyCmp());
        int length = nums.length;
        // 利用一个哈希表来统计数字的个数
        for(int i=0;i<length;++i)
        {
            if(!map.containsKey(nums[i]))
                map.put(nums[i],1);
            else
                map.put(nums[i],map.get(nums[i])+1);
        }
        // 将哈希表转化为优先队列
        for (Integer n: map.keySet())
        {
            priorityQueue.add(new Element(n,map.get(n)));
        }
        int ans[]=new int[k];
        for (int i=0;i<k;++i)
        {
            ans[i]=priorityQueue.poll().num;
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.TreeMap;
// 自定义元素
class Element
{
    int num;
    int count;
    public Element(int num,int count)
    {
        this.num=num;
        this.count=count;
    }

    @Override
    public String toString() {
        return "Element{" +
                "num=" + num +
                ", count=" + count +
                '}';
    }
}
// 自定义排序规则
class  MyCmp implements Comparator<Element>
{
    @Override
    public int compare(Element o1, Element o2) {
        return o2.count-o1.count;
    }
}
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        PriorityQueue<Element> priorityQueue = new PriorityQueue<>(new MyCmp());
        int length = nums.length;
        // 利用一个哈希表来统计数字的个数
        for(int i=0;i<length;++i)
        {
            if(!map.containsKey(nums[i]))
                map.put(nums[i],1);
            else
                map.put(nums[i],map.get(nums[i])+1);
        }
        // 将哈希表转化为优先队列
        for (Integer n: map.keySet())
        {
            priorityQueue.add(new Element(n,map.get(n)));
        }
        int ans[]=new int[k];
        for (int i=0;i<k;++i)
        {
            ans[i]=priorityQueue.poll().num;
        }
        return ans;
    }
}