find-k-pairs-with-smallest-sums

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given two integer arrays <code>nums1</code> and <code>nums2</code> sorted in non-decreasing&nbsp;order and an integer <code>k</code>.

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

Return the <code>k</code> pairs <code>(u1, v1), (u2, v2), ..., (uk, vk)</code> with the smallest sums.

&nbsp;
Example 1:

<pre>
Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: 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]
</pre>

Example 2:

<pre>
Input: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
Output: [[1,1],[1,1]]
Explanation: 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]
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums1.length, nums2.length &lt;= 105</code></li>
	<li><code>-109 &lt;= nums1[i], nums2[i] &lt;= 109</code></li>
	<li><code>nums1</code> and <code>nums2</code> both are sorted in non-decreasing order.</li>
	<li><code>1 &lt;= k &lt;= 104</code></li>
	<li><code>k &lt;=&nbsp;nums1.length *&nbsp;nums2.length</code></li>
</ul>

kSmallestPairs

Find K Pairs with Smallest Sums

Kth Smallest Element in a Sorted Matrix

kth-smallest-element-in-a-sorted-matrix

有序矩阵中第 K 小的元素

Find K-th Smallest Pair Distance

find-k-th-smallest-pair-distance

找出第 K 小的数对距离

Kth Smallest Product of Two Sorted Arrays

kth-smallest-product-of-two-sorted-arrays

两个有序数组的第 K 小乘积

Array

Heap (Priority Queue)

给定两个以 非递减顺序排列 的整数数组 <code>nums1</code> 和 <code>nums2</code>&nbsp;,&nbsp;以及一个整数 <code>k</code>&nbsp;。

定义一对值&nbsp;<code>(u,v)</code>，其中第一个元素来自&nbsp;<code>nums1</code>，第二个元素来自 <code>nums2</code>&nbsp;。

请找到和最小的 <code>k</code>&nbsp;个数对&nbsp;<code>(u1,v1)</code>, <code>&nbsp;(u2,v2)</code> &nbsp;... &nbsp;<code>(uk,vk)</code>&nbsp;。

&nbsp;

示例 1:

<pre>
输入: 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]
</pre>

示例 2:

<pre>
输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [[1,1],[1,1]]
解释: 返回序列中的前 2 对数：
&nbsp; [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
</pre>

&nbsp;

提示:

<ul>
	<li><code>1 &lt;= nums1.length, nums2.length &lt;= 105</code></li>
	<li><code>-109 &lt;= nums1[i], nums2[i] &lt;= 109</code></li>
	<li><code>nums1</code> 和 <code>nums2</code> 均为 升序排列</li>
	<li><meta charset="UTF-8" /><code>1 &lt;= k &lt;= 104</code></li>
	<li><code>k &lt;=&nbsp;nums1.length *&nbsp;nums2.length</code></li>
</ul>