【LeetCode】前 K 个高频元素（堆）

目录

1.题目要求：

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

2.解题思路：

代码展示：

---

1.题目要求：

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

示例 1:

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

示例 2:

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

提示：

• 1 <= nums.length <= 105
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

2.解题思路：

创建一个哈希表，用其存放数组中出现的元素以及每个元素出现的次数

        //用哈希表存储出现的元素，和出现的次数Map<Integer,Integer> map = new HashMap<>();for (int i:nums) {if(map.containsKey(i)){map.put(i,map.get(i) + 1);}else {map.put(i,1);}}

先创建一个类numOfTimes , 其中有两个属性，一个key值，一个k值出现的次数

//创建一个类，其中两个属性，一个k值，一个k值出现的次数
class numOfTimes{int key;int times;public numOfTimes(int key, int times) {this.key = key;this.times = times;}
}

写一个类numsSortWayOfTimes继承Comparator方法接口，重写compare方法（对numOfTimes对象进行排序比较的方式---key值出现的次数times的大小）

class numsSortWayOfTimes implements Comparator<numOfTimes> {@Overridepublic int compare(numOfTimes o1, numOfTimes o2) {return o1.times - o2.times;}
}

将map内的key值按照出现次数进行比大小

建立一个优先级队列大小为k,存储（元素与出现次数的）numOfTimes的对象

遍历队列后就会将出现次数最多的元素对象留在了堆中

        //将map内的key值按照出现次数进行比大小//建立一个优先级队列大小为k,存储（元素与出现次数的）numOfTimes的对象//遍历队列后就会将出现次数最多的元素留在了堆中Queue<numOfTimes> queue = new PriorityQueue<>(new numsSortWayOfTimes());//遍历map，将出现次数最高的前k个numOfTimes对象保存在堆中for (Map.Entry<Integer,Integer> entry:map.entrySet()) {queue.offer(new numOfTimes(entry.getKey(),entry.getValue()));if(queue.size() > k){queue.poll();}}

此时队列中存放的就是出现次数最多的元素对象
遍历队列将对象的key值保存在数组中，返回该数组即可

        //此时队列中存放的就是出现次数最多的元素//遍历队列将key值保存在数组中int[] res = new int[k];for(int i = 0; i < k; i++){res[i] = queue.poll().key;}return res;

代码展示：

import java.util.*;//创建一个类，其中两个属性，一个k值，一个k值出现的次数
class numOfTimes{int key;int times;public numOfTimes(int key, int times) {this.key = key;this.times = times;}
}//对numOfTimes进行排序比较的方式，（出现次数）
//继承Comparator接口重写compare方法
class numsSortWayOfTimes implements Comparator<numOfTimes> {@Overridepublic int compare(numOfTimes o1, numOfTimes o2) {return o1.times - o2.times;}
}public class Leetcode_347 {//给你一个整数数组 nums 和一个整数 k ，// 请你返回其中出现频率前 k 高的元素。// 你可以按 任意顺序 返回答案。
//    输入: nums = [1,1,1,2,2,3], k = 2
//    输出: [1,2]public int[] topKFrequent(int[] nums, int k) {//用哈希表存储出现的元素，和出现的次数Map<Integer,Integer> map = new HashMap<>();for (int i:nums) {if(map.containsKey(i)){map.put(i,map.get(i) + 1);}else {map.put(i,1);}}//将map内的key值按照出现次数进行比大小//建立一个优先级队列大小为k,存储（元素与出现次数的）numOfTimes的对象//遍历队列后就会将出现次数最多的元素留在了堆中Queue<numOfTimes> queue = new PriorityQueue<>(new numsSortWayOfTimes());//遍历map，将出现次数最高的前k个numOfTimes对象保存在堆中for (Map.Entry<Integer,Integer> entry:map.entrySet()) {queue.offer(new numOfTimes(entry.getKey(),entry.getValue()));if(queue.size() > k){queue.poll();}}//此时队列中存放的就是出现次数最多的元素//遍历队列将key值保存在数组中int[] res = new int[k];for(int i = 0; i < k; i++){res[i] = queue.poll().key;}return res;}
}