373. Find K Pairs with Smallest Sums

ningwang 发布于2019-08-16 10:35 / 2619人阅读

摘要：利用特点进行排序。我们需要构建一个数据结构，一个表示在的位置，一个表示在的位置，他们的和，用来排序。我们首先向里，和所有的元素的和。每次我们一组数，然后增加的会自然的进行排序。

Given nums1 = [1,7,11], nums2 = [2,4,6],  k = 3

Return: [1,2],[1,4],[1,6]

The first 3 pairs are returned from the sequence:
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

利用pq特点进行排序。
我们需要构建一个数据结构，一个pos表示在nums1的位置，一个pos表示在nums2的位置，他们的和，用来排序。
我们首先向PQ里offer，nums1[0] 和 所有nums2的元素的和。
每次我们poll一组数，然后增加nums1的pos, pq会自然的进行排序。操作K次就行了。

public class Solution {
    public List kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List res = new ArrayList();
        if(nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0 || k < 0) return res;
        PriorityQueue pq = new PriorityQueue(new Comparator(){
            public int compare(int[] a, int[] b){
                return a[2] - b[2];
            }
        });
        
        int m = nums1.length, n = nums2.length;
        for(int i = 0; i < n; i++){
            // t[0] pos in nums1, t[1] pos in nums2, val nums[t[0]]+nums[t[1]]
            pq.offer(new int[]{0, i, nums1[0] + nums2[i]});
        }
        
        for(int i = 0; i < Math.min(k, m*n); i++){
            int[] t = pq.poll();
            res.add(new int[]{nums1[t[0]], nums2[t[1]]});
            if(t[0] == m-1) continue;
            pq.offer(new int[]{ t[0] + 1, t[1], nums1[t[0] + 1] + nums2[t[1]] });
        }
        
        return res;
    }
}

海外云主机服务器托管 Sums Smallest pairs with

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70081.html

373. Find K Pairs with Smallest Sums

摘要：题目链接先把一组里面和另外一组最小元素的组合放进，然后每次出和最小的，同时放进去有可能成为第二小的组合，即当前元素的下一个和元素的组合。 373. Find K Pairs with Smallest Sums 题目链接：https://leetcode.com/problems... greedy: 先把一组x里面和另外一组y最小元素的组合放进heap，然后每次poll出和最小的，同...

wing324 2019-08-14 17:25 评论0 收藏0
leetcode373. Find K Pairs with Smallest Sums

摘要：题目要求两个单调递增的整数数组，现分别从数组和数组中取一个数字构成数对，求找到个和最小的数对。思路这题采用最大堆作为辅助的数据结构能够完美的解决我们的问题。每从堆中取走一个数对，就插入，从而确保堆中的数对都可以从小到大遍历到。题目要求 You are given two integer arrays nums1 and nums2 sorted in ascending order ...

Lavender 2019-08-16 13:55 评论0 收藏0
378. Kth Smallest Element in a Sorted Matrix

摘要：复杂度是，其中。这做法和异曲同工。看了网上给的解法，没有二分，二分的是结果。每次找到一个，然后求比它小的元素的个数，根据个数大于还是小于来二分。参考算的时候可以优化 378. Kth Smallest Element in a Sorted Matrix 题目链接：https://leetcode.com/problems... 求矩阵里面第k小的数，首先比较容易想到的是用heap来做...

Y3G 2019-08-14 17:28 评论0 收藏0