前k个高频元素 Posted on 2021-07-24 00:00:00 2021-07-24 00:00:00 by Author 摘要 给定一个数组，你能找出数组中前K个比较大的数吗？？？？？ # 前k个高频元素 1. 题目描述 - 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。 - 条件：可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。 算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。 你可以按任意顺序返回答案。 2. 示例描述 - 示例一 - 输入： nums = [1,1,1,2,2,3], k = 2 - 输出：[1,2] - 示例二 - 输入：nums = [3, 2, 1, 4, 2, 3, 5, 2], k=2 - 输出：[3, 2] 3. 解题思路 - 当我看到这道题的时候，有点看不懂题目讲的啥。但是看完了描述，才慢慢明白，就是找出数组中元素出现次数最多的前k个元素。 - 题目说过k个元素是唯一的，说明每一个数组只能存在一组k个高频元素的数组。最简单的办法就是定义一个Map<key,val> 集合，key存储的数组元素的值，val就是存储key出现的次数，然后我们在根据val进行排序，找出前k个元素即可。又因为我们只用找出前K个高频元素即可，我们这里可以选择建立堆，然后只用去取堆里的前k个元素即可。 - 首先我们遍历整个数组，如果map中key存在就在val上+1，如果key不存在，把key加入map中，并且val=1。遍历完整个数组，那么map集合也就建立好了。之后对频率进行排序，也就是对map中所有的val进行排序，这里我们可以定义一个小堆，这里定义小堆我们可以用有限队列进行定义，队列中存放k个元素，即存放map中的 key,每次进入一个元素的时候，我们就进行对队列进行排序(以队列元素的频率进行排序)，如果队列中元素大于k个，那么我们只用比较当前元素的频率是否大于队头元素的频率，如果大于就先移除队头元素，在加入当前的元素，因为我们始终维持队列中有k个元素，并且队列中元素是以频率从小到达来排列的。遍历完成之后，队列中就存放了前k个高频元素了，最后返回结果即可。 - 具体代码以及每步的解释见如下代码。注释里面可能会回答你的疑惑，记得认真看完哦！！！！ 4. 代码示例 ```java public int[] topKFrequent(int[] nums, int k) { //建立一个Map集合，key为数组的元素，val为元素出现的频率 Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { //如果map不包含该元素，则加入map中，val设置为1 if (!map.containsKey(nums[i])) { map.put(nums[i], 1); } else {//否则val+1 map.put(nums[i], map.get(nums[i]) + 1); } } //建立一个小堆 遍历map，用最小堆保存频率最大的k个元素 //有的人可能看不懂这段代码为啥是用优先队列来建立小堆的 //我们知道队列的特点是先进先出，所以当我们在进行对数组元素频率进行排序的时候 //当我们进入的元素的频率小于该元素之前元素频率最小的数的时候，那么最小的数就可以移除了 //而移除的这个数是比当前要进入的这个数后来，所以队列的这个特点刚好符号我们的需求，所以用队列来当作小堆 //而这个队列中始终维护有k个元素，并且队列中元素是以频率从小到达来排列的 //这样就能实现小堆了 PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() { //这个是实现当加入元素的时候，对队列进行从小到大排列 //所以每加入一个元素，就进行排序一次，就始终保持队列是从小到大排列的 //始终维护这小堆，以便后续的操作 @Override public int compare(Integer a, Integer b) { return map.get(a) - map.get(b); } }); //然后遍历map所有的key for (Integer key : map.keySet()) { //之前我们说了，队中始终存放k个元素，如果不够就往里面加 //加入的过程中，就会进行排序，建立小堆 if (pq.size() < k) { pq.add(key); } //如果队列中的元素个数大于k个，那么我们比较队列的队头元素的频率 //是否小于当前元素的频率，如果小的话，那我们就把该元素加入队列中 //加入之后，队列就会自动根据加入元素的频率进行排序,以便后续的操作 else if (map.get(key) > map.get(pq.peek())) { //因为始终保持队列有k个元素，所有要加入一个元素就必须移除一个元素 //而队头的元素出现频率最小，所以就移除队头的元素(队列中是以元素频率从小到大排列的，所以队头元素的频率最小，理应被移除) pq.remove(); //最后加入要进入队列的元素 pq.add(key); } } // 取出最小堆中的元素 int [] res = new int[k]; int i=0; //队列中有k个元素,所以把队列中所有元素加入结果集中，题目说结果集中元素顺序随意 while (!pq.isEmpty()) { res[i++]=pq.remove(); } //返回最后结果 return res; } ```
{{ item.content }}
{{ child.content }}