Jiaming Zhang's Blog
0%

算法-堆

发表于 更新于 分类于

堆相关算法题

347. 前 K 个高频元素

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

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
class Solution {
    class Number {
        int val;
        int freq;
        Number(int val, int freq) {
            this.val = val;
            this.freq = freq;
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return nums;
        }
        // 统计数组中每个数值出现的次数
        PriorityQueue<Number> priorityQueue = new PriorityQueue<>((o1, o2) -> o2.freq - o1.freq);
        Map<Integer, Number> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], new Number(nums[i], 0));
            }
            Number number = map.get(nums[i]);
            number.freq ++;
        }
        priorityQueue.addAll(map.values());
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            Number number = priorityQueue.poll();
            ans[i] = number.val;
        }
//        System.out.println(Arrays.toString(ans));
        return ans;
    }
}

264. 丑数 II

给你一个整数 n ，请你找出并返回第 n 个 丑数 。丑数 就是只包含质因数 2、3 和 5 的正整数。

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
class Solution {
    public int nthUglyNumber(int n) {
        PriorityQueue<Long> priorityQueue = new PriorityQueue<>();
        long num = 1L;
        priorityQueue.add(num);
        Set<Long> uglyNumberSet = new HashSet<>();
        uglyNumberSet.add(num);
        for (int i = 0; i < n; i++) {
            num = priorityQueue.poll();
            if (!uglyNumberSet.contains(num * 2)) {
                priorityQueue.add(num * 2);
                uglyNumberSet.add(num * 2);
            }
            if (!uglyNumberSet.contains(num * 3)) {
                priorityQueue.add(num * 3);
                uglyNumberSet.add(num * 3);
            }
            if (!uglyNumberSet.contains(num * 5)) {
                priorityQueue.add(num * 5);
                uglyNumberSet.add(num * 5);
            }
        }
        return (int) num;
    }
}