leetcode刷题：栈与队列06（前 K 个高频元素）

347.前 K 个高频元素

力扣题目链接

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

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

示例 2:

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

提示：

• 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
• 你的算法的时间复杂度必须优于 $O(n\log n)$ , n 是数组的大小。
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
• 你可以按任意顺序返回答案。

又是一个中等题一发入魂，飘了hhhhh
思路：
哈希表计算每个数字出现的次数
键、值分别放到两个数组，按值排序，键镜像同步变换位置
返回前K个数字。

package com.programmercarl.stacks_queues;
import java.util.HashMap;

/** * @ClassName TopKFrequent * @Descriotion TODO * @Author nitaotao * @Date 2022/6/30 14:13 * @Version 1.0 * https://leetcode.cn/problems/top-k-frequent-elements/ * 347. 前 K 个高频元素 **/
public class TopKFrequent {
    
    public static int[] topKFrequent(int[] nums, int k) {
    
        /** * 思路： * 哈希表计数 */
        HashMap<Integer, Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
    
            if (map.containsKey(nums[i])) {
    
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
    
                map.put(nums[i], 1);
            }
        }
        int[] keys = new int[map.size()];
        int[] values = new int[map.size()];
        int index = 0;
        for (Integer key : map.keySet()) {
    
            keys[index] = key;
            values[index] = map.get(key);
            index++;
        }
        //value 排序，key 镜像同步交换 
        for (int i = 0; i < values.length-1; i++) {
    
            for (int j = i+1; j < values.length; j++) {
    
                if (values[i] < values[j]) {
    
                    int tempValue = values[i];
                    values[i] = values[j];
                    values[j] = tempValue;

                    int tempKey = keys[i];
                    keys[i] = keys[j];
                    keys[j] = tempKey;
                }
            }
        }
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
    
            result[i] = keys[i];
        }
        return result;
    }
}

看题解还有另一个思路，是我们之前上课时老师讲的思路，大顶堆思想。

    public static int[] topKFrequent(int[] nums, int k) {
    
        /** * 思路： * 哈希表计数 */
        HashMap<Integer, Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
    
            if (map.containsKey(nums[i])) {
    
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
    
                map.put(nums[i], 1);
            }
        }
        //大顶堆思想
        //优先级队列，按值大小排序
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());
        for(Map.Entry<Integer,Integer>entry : map.entrySet()) {
    
            queue.offer(entry);
            //只保留前k个数
            if (queue.size() > k) {
    
                queue.poll();
            }
        }
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
    
            result[i] = queue.poll().getKey();
        }
        return result;
    }