做网站诱导网站,wordpress 主菜单插件,集团做网站优势,淄博营销型网站建设公司目录
1.题目要求#xff1a;
给你一个整数数组 nums 和一个整数 k #xff0c;请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
2.解题思路#xff1a;
代码展示#xff1a; 1.题目要求#xff1a;
给你一个整数数组 nums 和一个整数 k #xff0…目录
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 105k 的取值范围是 [1, 数组中不相同的元素的个数]题目数据保证答案唯一换句话说数组中前 k 个高频元素的集合是唯一的2.解题思路
创建一个哈希表用其存放数组中出现的元素以及每个元素出现的次数 //用哈希表存储出现的元素和出现的次数MapInteger,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 ComparatornumOfTimes {Overridepublic int compare(numOfTimes o1, numOfTimes o2) {return o1.times - o2.times;}
}将map内的key值按照出现次数进行比大小
建立一个优先级队列大小为k,存储元素与出现次数的numOfTimes的对象
遍历队列后就会将出现次数最多的元素对象留在了堆中 //将map内的key值按照出现次数进行比大小//建立一个优先级队列大小为k,存储元素与出现次数的numOfTimes的对象//遍历队列后就会将出现次数最多的元素留在了堆中QueuenumOfTimes queue new PriorityQueue(new numsSortWayOfTimes());//遍历map将出现次数最高的前k个numOfTimes对象保存在堆中for (Map.EntryInteger,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 ComparatornumOfTimes {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) {//用哈希表存储出现的元素和出现的次数MapInteger,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的对象//遍历队列后就会将出现次数最多的元素留在了堆中QueuenumOfTimes queue new PriorityQueue(new numsSortWayOfTimes());//遍历map将出现次数最高的前k个numOfTimes对象保存在堆中for (Map.EntryInteger,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;}
}
