首页 > itarticle > [leetcode]find k pairs with smallest sums

[leetcode]find k pairs with smallest sums

admin 11月 12, 2020 0

题目描述

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums.

Example 1:

1
2
3
4
5
6
 
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]

Example 2:

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

Return: [1,1],[1,1]

The first 2 pairs are returned from the sequence:
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

Example 3:

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

Return: [1,3],[2,3]

All possible pairs are returned from the sequence:
[1,3],[2,3]

解题思路

类似两路归并排序

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
 
public class  {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<Tuple> pq = new PriorityQueue<>();
        List<int[]> res = new ArrayList<>();

        if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0 || k <= 0) return res;

        for(int j = 0; j < nums2.length && j < k; j++) pq.offer(new Tuple(0,j,nums1[0]+nums2[j]));

        for(int i = 0; i < Math.min(k, nums1.length*nums2.length); i++){
            Tuple temp = pq.poll();
            res.add(new int[]{nums1[temp.x], nums2[temp.y]});
            if(temp.x == nums1.length - 1) continue;
            pq.offer(new Tuple(temp.x+1, temp.y, nums1[temp.x+1]+nums2[temp.y]));
        }
        return res;
    }

}

class Tuple implements Comparable<Tuple>{
    int x,y,val;

    public Tuple(int x, int y, int val){
        this.x = x;
        this.y = y;
        this.val = val;
    }

    public int compareTo(Tuple that){
        return this.val - that.val;
    }
}

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能