topk算法-leetcode java题解

topk算法-leetcode java题解

java优先队列

PriorityQueue(优先队列），一个基于优先级堆的无界优先级队列。

通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值）

实际上是一个堆（不指定Comparator时默认为最小堆），通过传入自定义的Comparator函数可以实现大顶堆。

PriorityQueue是非线程安全的，所以Java提供了PriorityBlockingQueue（实现BlockingQueue接口）用于Java多线程环境

优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加

小顶堆

//默认容量为11
PriorityQueue minHeap = new PriorityQueue();

//小根堆实例
PriorityQueue heap = new PriorityQueue<>(new Comparator() {
    @Override
    public int compare(Integer o1, Integer o2){
        return o1 - o2;
    }
});

// 将数组元素放入堆
int[] arr = {6,5,2,3,1,4};

for (int i :arr) {
    heap.offer(i);
}
System.out.println(heap);

int index = 0;
// 每次将堆顶元素放入数组，并删除堆顶元素，相当于每次从剩余堆中取最大值
for (int i = 0; i < arr.length; i++) {
    arr[index++] = (Integer) heap.poll();
}

for (int i :arr) {
    System.out.print(i + " ");  // 1 2 3 4 5 6 
}
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

可能的初始化形式

// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
PriorityQueue queue = new PriorityQueue(new Comparator() {
    public int compare(int[] m, int[] n) {
        return m[1] - n[1];
    }
});

PriorityQueue> queue = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());

1
2
3
4
5
6
7
8
9

大顶堆

//容量11 
PriorityQueue maxHeap = new PriorityQueue(11,new Comparator(){
    @Override
    public int compare(Integer i1,Integer i2){
        return i2 - i1;
    }
});
//大顶堆实例
PriorityQueue queue = new PriorityQueue<>(new Comparator() {
    @Override
    public int compare(Student o1, Student o2){
        return o2.getId() - o1.getId();
    }
});
1
2
3
4
5
6
7
8
9
10
11
12
13
14

取最小的N个数：使用大顶堆
先出大数：使用大顶堆

取最大的N个数：使用小顶堆
先出小数：使用小顶堆

常用方法

public boolean add(E e); //在队尾插入元素，插入失败时抛出异常，并调整堆结构
public boolean offer(E e); //在队尾插入元素，插入失败时抛出false，并调整堆结构

public E remove(); //获取队头元素并删除，并返回，失败时前者抛出异常，再调整堆结构
public E poll(); //获取队头元素并删除，并返回，失败时前者抛出null，再调整堆结构

public E element(); //返回队头元素（不删除），失败时前者抛出异常
public E peek()；//返回队头元素（不删除），失败时前者抛出null

public boolean isEmpty(); //判断队列是否为空
public int size(); //获取队列中元素个数
public void clear(); //清空队列
public boolean contains(Object o); //判断队列中是否包含指定元素（从队头到队尾遍历）
public Iterator iterator(); //迭代器
1
2
3
4
5
6
7
8
9
10
11
12
13
14

leetcode Num17.14:找数组中最小k个数

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]
1
2
3

找出数组中最小的k个数。以任意顺序返回这k个数均可（取小数用大堆）

    public int[] smallestK(int[] arr, int k) {
        if(arr.length == 0|| k == 0){
            return new int[0];
        }

        PriorityQueue queue = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        for(int i : arr){
            if(queue.size() < k){
                queue.offer(i);
            }else{
                int peek = queue.peek();
                if(i > peek){
                    //元素>堆顶元素，不入队，进入下一个循环
                    continue;
                }else{
                    queue.poll();
                    queue.offer(i);
                }
            }
        }

        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }

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

leetcode Num347:前k个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。
你可以按 任意顺序 返回答案。
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
1
2
3
4

参数为int

    public int[] topKFrequent(int[] nums, int k) {
        Map map = new HashMap<>();
        for(int i : nums){
            if(map.containsKey(i)){
                int num = map.get(i) + 1;
                map.put(i,num);
            }else {
                map.put(i,1);
            }
        }

        // 遍历map，用最小堆保存频率最大的k个元素
        PriorityQueue pq = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });
        for (Integer key : map.keySet()) {
            if (pq.size() < k) {
                pq.add(key);
            } else if (map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }

        int[] res = new int[k];
        for(int i = 0; i < k; i++){
            res[i] = pq.poll();
        }
        return res;

    }
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

参数为int[]

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map occurrences = new HashMap();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }

        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        PriorityQueue queue = new PriorityQueue(new Comparator() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });
        for (Map.Entry entry : occurrences.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            } else {
                queue.offer(new int[]{num, count});
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }
}
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

新建参数的实体类

class Solution {
    /**
     * 利用优先队列
     * 小根堆，顶部为第k个大
     */

    class Pair {
        int value;  //存储的元素
        int freq;   //元素出现的频次

        Pair(int value, int freq) {
            this.value = value;
            this.freq = freq;
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        Map map = new HashMap<>();
        for (int d : nums) {
            map.put(d, map.getOrDefault(d, 0) + 1);
        }

        PriorityQueue queue = new PriorityQueue<>(new Comparator() {//传入比较器
            @Override
            public int compare(Pair o1, Pair o2) {
                return o1.freq - o2.freq;
            }
        });
        for (Map.Entry entry : map.entrySet()) {
            if (queue.size() == k) {
                if (entry.getValue() > queue.peek().freq) {
                    queue.poll();
                    queue.add(new Pair(entry.getKey(), entry.getValue()));
                }
            } else {
                queue.add(new Pair(entry.getKey(), entry.getValue()));
            }
        }

        int[] ret = new int[k];
        //此时,最小堆内的元素就是需要的元素，依次出队
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll().value;
        }
        return ret;
    }

}
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

leetcode 373. 查找和最小的 K 对数字

给定两个以 升序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  ...  (uk,vk) 。

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
     [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 方式一：结果为堆中元素

  对于单个序列的TopK问题，首先将序列的前 k 个元素添加到大根堆(降序)中
  然后遍历剩下的 n - k 个元素，逐个判断其与堆顶元素的大小，当前元素小时，取出堆顶，加入当前元素(堆调整)
  最终堆中剩余的 k 个元素就是TopK

• 方式二：结果为堆中每次取出的元素

  对于多个序列的TopK问题，如本题是有两个独立的数组，需要先对各个子序列排序
  接着同样在小根堆(升序)中维护对应序列个数个元素，然后每次取出堆顶元素，并加入当前堆顶元素(最小值)所在序列的下一个值，一共进行 k 次
  取出的元素组成的集合( k 个)就是TopK，这种方式也成为多路归并，常见于大文件排序、海量数据排序等场景(面试热点)

（1）结果为堆中元素

    public static List> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue queue = new PriorityQueue<>(new Comparator() {//传入比较器
            @Override
            public int compare(Pair o1, Pair o2) {
                return (o2.n1 + o2.n2) - (o1.n1 + o1.n2);
            }
        });

        for (int i = 0; i < Math.min(nums1.length,k); i++) {
            for (int j = 0; j < Math.min(nums2.length,k); j++) {
                if(queue.size() < k){
                    queue.offer(new Pair(nums1[i],nums2[j]));
                }else {
                    int sum = nums1[i] + nums2[j];
                    Pair pair = queue.peek();
                    if(sum < pair.n1 + pair.n2){
                        queue.poll();
                        queue.offer(new Pair(nums1[i], nums2[j]));
                    }
                }
            }
        }
        
        List> ret = new ArrayList<>();
        for (int i = 0; i < k && (!queue.isEmpty()); i++) {
            List temp = new ArrayList<>();
            Pair pair = queue.poll();
            temp.add(pair.n1);
            temp.add(pair.n2);
            ret.add(temp);
        }
        return ret;

    }

    static class Pair{
        //第一个数组的值
        int n1;
        //第二个数组的值
        int n2;

         Pair(int n1, int n2) {
            this.n1 = n1;
            this.n2 = n2;
         }
    }
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

（2）结果为堆中每次取出的元素

    public List> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        // 优先级队列，保存 [index1, index2]
        PriorityQueue heap = new PriorityQueue<>(new Comparator() {//传入比较器
            @Override
            public int compare(int[] o1, int[] o2) {
                return (nums1[o1[0]] + nums2[o1[1]]) - (nums1[o2[0]] + nums2[o2[1]]);
            }
        });

        // 把 nums1 的所有索引入队，nums2 的索引初始时都是 0
        for (int i = 0; i < Math.min(k, nums1.length); i++) {
            heap.offer(new int[] {i, 0});
        }

        List> ans = new ArrayList<>();

        while (k-- > 0 && !heap.isEmpty()) {
            int[] pos = heap.poll();
            List list = new ArrayList<>();
            list.add(nums1[pos[0]]);
            list.add(nums2[pos[1]]);
            ans.add(list);
            if (pos[1] + 1 < nums2.length) {
                heap.offer(new int[]{pos[0], pos[1] + 1});
            }
        }
        
        return ans;
    } 
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

leetcode 692. 前K个高频单词

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。

1
2
3
4
5
6
7
8
9

相等次数的值的顺序比较，按照字母
x.compareTo(y)，y大返回1

    public List topKFrequent(String[] words, int k) {
        // 1.先用哈希表统计单词出现的频率
        Map count = new HashMap();
        for (String word : words) {
            count.put(word, count.getOrDefault(word, 0) + 1);
        }
        // 2.构建小根堆 这里需要自己构建比较规则 此处为 lambda 写法 Java 的优先队列默认实现就是小根堆
        PriorityQueue minHeap = new PriorityQueue<>((s1, s2) -> {
            if (count.get(s1).equals(count.get(s2))) {
                return s2.compareTo(s1);
            } else {
                return count.get(s1) - count.get(s2);
            }
        });
        // 3.依次向堆加入元素。
        for (String s : count.keySet()) {
            minHeap.offer(s);
            // 当堆中元素个数大于 k 个的时候，需要弹出堆顶最小的元素。
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        // 4.依次弹出堆中的 K 个元素，放入结果集合中。
        List res = new ArrayList(k);
        while (minHeap.size() > 0) {
            res.add(minHeap.poll());
        }
        // 5.注意最后需要反转元素的顺序。
        Collections.reverse(res);
        return res;
    }        
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

    public List topKFrequent(String[] words, int k) {
        Map map = new HashMap<>();
        for (String d : words) {
            map.put(d, map.getOrDefault(d, 0) + 1);
        }

        PriorityQueue queue = new PriorityQueue<>(new Comparator() {//传入比较器
            @Override
            public int compare(Pair s1, Pair s2) {
                if (s1.freq == s2.freq) {
                    // 如果指定的数与参数相等返回 0
                    return s2.value.compareTo(s1.value);
                } else {
                    return s1.freq - s2.freq;
                }
            }
        });
        for (Map.Entry entry : map.entrySet()) {
            queue.offer(new Pair(entry.getKey(), entry.getValue()));
            if (queue.size() > k) {
                queue.poll();
            }
        }

        List res = new LinkedList<>();

        while (!queue.isEmpty()){
            res.add(queue.poll().value);
        }
        Collections.reverse(res);
        return res;

    }

    static class Pair {
        String value;  //存储的元素
        int freq;   //元素出现的频次

        Pair(String value, int freq) {
            this.value = value;
            this.freq = freq;
        }
    }
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

leetcode 1046. 最后一块石头的重量

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0

输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

要弹出最大的数，用大根堆

    public int lastStoneWeight(int[] stones) {
        PriorityQueue queue = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        for (int stone : stones) {
            queue.offer(stone);
        }

        while (queue.size() > 1) {
            int a = queue.poll();
            int b = queue.poll();
            if (a > b) {
                queue.offer(a - b);
            }
        }

        if(queue.isEmpty()){
            return 0;
        }else{
            return queue.poll();
        }

    }
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

leetcode 2146. 价格范围内最高排名的 K 样物品

给你一个下标从 0 开始的二维整数数组 grid ，它的大小为 m x n ，表示一个商店中物品的分布图。数组中的整数含义为：

0 表示无法穿越的一堵墙。
1 表示可以自由通过的一个空格子。
所有其他正整数表示该格子内的一样物品的价格。你可以自由经过这些格子。
从一个格子走到上下左右相邻格子花费 1 步。

同时给你一个整数数组 pricing 和 start ，其中 pricing = [low, high] 且 start = [row, col] ，表示你开始位置为 (row, col) ，同时你只对物品价格在 闭区间 [low, high] 之内的物品感兴趣。同时给你一个整数 k 。

你想知道给定范围 内 且 排名最高 的 k 件物品的 位置 。排名按照优先级从高到低的以下规则制定：

距离：定义为从 start 到一件物品的最短路径需要的步数（较近 距离的排名更高）。
价格：较低 价格的物品有更高优先级，但只考虑在给定范围之内的价格。
行坐标：较小 行坐标的有更高优先级。
列坐标：较小 列坐标的有更高优先级。
请你返回给定价格内排名最高的 k 件物品的坐标，将它们按照排名排序后返回。如果给定价格内少于 k 件物品，那么请将它们的坐标 全部 返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输入：grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3
输出：[[0,1],[1,1],[2,1]]
解释：起点为 (0,0) 。
价格范围为 [2,5] ，我们可以选择的物品坐标为 (0,1)，(1,1)，(2,1) 和 (2,2) 。
这些物品的排名为：
- (0,1) 距离为 1
- (1,1) 距离为 2
- (2,1) 距离为 3
- (2,2) 距离为 4
所以，给定价格范围内排名最高的 3 件物品的坐标为 (0,1)，(1,1) 和 (2,1) 。

输入：grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3
输出：[[2,1],[2,0]]
解释：起点为 (0,0) 。
价格范围为 [2,3] ，我们可以选择的物品坐标为 (2,0) 和 (2,1) 。
这些物品的排名为：
- (2,1) 距离为 5
- (2,0) 距离为 6
所以，给定价格范围内排名最高的 2 件物品的坐标为 (2,1) 和 (2,0) 。
注意，k = 3 但给定价格范围内只有 2 件物品。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

使用BFS查询，使用小根队存储结果
排序条件按照先后进行if-else判断

    public List> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {
        int[][] direct = new int[][]{{-1,0},{0,-1},{1,0},{0,1}};
        int m = grid.length;
        int n = grid[0].length;

        PriorityQueue pQueue = new PriorityQueue<>((a,b)->{
            if(a[2] != b[2]) return a[2] - b[2];
            if(a[3] != b[3]) return a[3] - b[3];
            if(a[4] != b[4]) return a[4] - b[4];
            return a[5] - b[5];
        });

        Queue queue = new LinkedList<>();
        int f = grid[start[0]][start[1]];
        // 起点满足
        if(f > 1 && f >= pricing[0] && f<= pricing[1]){
            pQueue.offer(new int[]{start[0],start[1],0,f,start[0],start[1]});
        }
        queue.offer(start);
        grid[start[0]][start[1]] = -1;
        
        int step = 0;
        while(!queue.isEmpty()){
            int sz = queue.size();
            step ++;
            for(int i = 0; i < sz; i++){
                int[] arr = queue.poll();
                for(int j = 0; j < direct.length; j++){
                    int x = arr[0] + direct[j][0];
                    int y = arr[1] + direct[j][1];
                    if(x < 0 || x >=m || y < 0 || y >= n || grid[x][y] < 1){
                        continue;
                    }
                    if(grid[x][y] >= pricing[0] && grid[x][y]<= pricing[1]){
                        pQueue.offer(new int[]{x,y,step,grid[x][y],x,y});
                    }
                    grid[x][y] = -1;
                    queue.offer(new int[]{x,y});
                }
            }
        }

        List> ans = new ArrayList<>();
        k = Math.min(k,pQueue.size());
        for(int i=0; i< k; i++){
            int[] arr = pQueue.poll();
            ans.add(Arrays.asList(arr[0],arr[1]));
        }
        return ans;
    }
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