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;
    }
}

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

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

    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;
    }
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