373.查找和最小的k对数字

发表于： 分类于：
字数： 1258 阅读：≈ 3分钟

✨ 373.查找和最小的k对数字

给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。

请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。

思路

基本思想

为了求出所有符合要求的数对，最简单的办法就是先将所有的数对先求出来，然后再利用堆排序求出前k个数对，但是这样时间复杂度太高，主要的问题就是出在要将所有的数对都求出来，出现了很多的冗余，其实完全可以只求出部分数对，这里有一个前提，最小的数对的索引一定是[0,0]，最大的数对的索引一定是[nums1.length,nums2.length]，而当选择了第n个数对之后，下一个数对的索引是在当前数对的索引基础上递增得来的。假设当前数对的索引为[x,y]，那么下一个数对的候选索引一定是[x+1,y]和[x,y+1]。

有了索引递增的概念之后，为了求出前k个和最小的数对，我们直接将索引加入优先级队列中，比较规则是当前的索引对应的数对和小的元素在前面，大的元素在后面，这样每次取出来的都是当前最小的数对。在取出一个数对元素之后，需要加入下一个候选的数对，此时需要注意，不能直接加入，否则会出现重复元素

例如当前选择的索引为[1,2]，那么加入的候选数对为[1,3]和[2,2]，如果后面某一步选择了[2,1]，那么就会重复加入[2,2]这个数对，这是因为数对的索引是同步变化的，没有固定住其中一个，为了去掉重复索引，我们选择将其中一个索引固定住，也就是先将部分元素加入优先级队列

1
2
3

for(int i=0;i<Math.min(nums1.length,k);++i){
    queue.add(new int[]{i,0});
}

加入之后，第一个位置的索引固定为最大值，这样就不会同步变化，也就不会出现重复的索引了

核心就是利用优先级队列可以对元素排序的思想，每次从中取出当前和最小的数对，并将下一步的候选下标加入

类似的题目还有 786. 第 K 个最小的素数分数

执行流程

  1. 设计一个优先级队列，排序规则根据下标对应的数对和的大小升序排列
  2. 先将部分下标加入优先级队列中，目的是为了固定一个下标不变，防止两个下标同时变化导致出现重复元素
  3. 每次从优先级队列中取出当前最小的数对元素，然后加入下一步的候选元素
  4. 取出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

class Solution {
    //针对两个数组都执行堆排序，然后从中取出前k个最小的元素组成一队
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //每次入队的元素都是下一次候选的元素
        //优先级队列中保存的是索引
        //索引对应的值相加小的在前面
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> ((nums1[a[0]] + nums2[a[1]]) - (nums1[b[0]] + nums2[b[1]])));
        List<List<Integer>> res = new ArrayList<>();
        //防止出现重复元素
        for(int i=0;i<Math.min(nums1.length,k);++i){
            queue.add(new int[]{i,0});
        }
        for (int i = 0; i < k; ++i) {
            if (queue.size() > 0) {
                int[] indexs = queue.poll();
                List<Integer> temp = new ArrayList<>();
                //结果容器中保存的是索引对应的值
                temp.add((nums1[indexs[0]]));
                temp.add((nums2[indexs[1]]));
                res.add(temp);
                //索引符合要求就加入优先级队列
                if (indexs[0] < nums1.length && indexs[1] + 1 < nums2.length) {
                    queue.add(new int[]{indexs[0], indexs[1] + 1});
                }
            } else {
                break;
            }
        }
        return res;
    }
}

总结

核心就是利用优先级队列存储数对的下标，然后排序规则按照数对和的大小升序排列，为了解决重复元素的问题，先将部分下标组合加入队列中，重点需要注意上面描述中的 “假设当前数对的索引为[x,y]，那么下一个数对的候选索引一定是[x+1,y]和[x,y+1]。”