find-k-pairs-with-smallest-sums

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

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>