leetcode Find K Pairs with Smallest Sums

leetcode Find K Pairs with Smallest Sums

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:

Example 2:

Example 3:

题目地址:leetcode Find K Pairs with Smallest Sums

题意:给定两个已排好序的数组,要求从两个数组中分别取出一个数,构成一个对,求所有能组成的对中,最小的K个。

思路:

最直接的思路是把全部的数都组合一下,然后维护一个大小为k的最大堆 这样复杂度O(m*n*logk)

其实还可以维护一个最小堆,每次取出堆顶的元素,然后把该元素相邻结点加入进去。这样能保证最小。

 

维护一个堆.

C++

 

 

本题是leetcode 373  Find K Pairs with Smallest Sums 题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Find K Pairs with Smallest Sums
本文地址:https://www.hrwhisper.me/leetcode-find-k-pairs-smallest-sums/

听说帅的人已经打赏了

Leetcode , . permalink.

2 thoughts on “leetcode Find K Pairs with Smallest Sums

  1. 用两个指针, 分别指向两个有序数组当前 index, i, j,
    res.push_back(i, j)
    if(a[i]+b[j+1] > a[i+1]+b[j]) i++;
    else j++; // need to judge if out of index.

    复杂度应该是 O(m+n) O(k) 吧 ?

Leave a Reply

Your email address will not be published. Required fields are marked *