Files
2020-08-09 00:39:24 +08:00

52 lines
2.7 KiB
Markdown
Executable File
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

# [373. Find K Pairs with Smallest Sums](https://leetcode.com/problems/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:**
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]
**Example 2:**
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]
**Example 3:**
Input: nums1 = [1,2], nums2 = [3], k = 3
Output: [1,3],[2,3]
Explanation: All possible pairs are returned from the sequence: [1,3],[2,3]
## 题目大意
给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。
定义一对值 (u,v)其中第一个元素来自 nums1第二个元素来自 nums2。
找到和最小的 k 对数字 (u1,v1), (u2,v2) ... (uk,vk)。
## 解题思路
- 给出 2 个数组,和数字 k要求找到 k 个数值对,数值对两个数的和最小。
- 这一题咋一看可以用二分搜索,两个数组两个组合有 `m * n` 个数值对。然后找到最小的和,最大的和,在这个范围内进行二分搜索,每分出一个 `mid`,再去找比 `mid` 小的数值对有多少个,如果个数小于 `k` 个,那么在右区间上继续二分,如果个数大于 `k` 个,那么在左区间上继续二分。到目前为止,这个思路看似可行。但是每次搜索的数值对是无序的。这会导致最终出现错误的结果。例如 `mid = 10` 的时候,小于 10 的和有 22 个,而 `k = 25` 。这说明 `mid` 偏小,`mid` 增大,`mid = 11` 的时候,小于 11 的和有 30 个,而 `k = 25` 。这时候应该从这 30 个和中取前 25 个。但是我们遍历数值对的时候,和并不是从小到大排序的。这时候还需要额外对这 30 个候选值进行排序。这样时间复杂度又增大了。
- 可以先用暴力解法解答。将所有的和都遍历出来,排序以后,取前 k 个。这个暴力方法可以 AC。
- 本题最优解应该是优先队列。维护一个最小堆。把数值对的和放在这个最小堆中,不断的 pop 出 k 个最小值到数组中,即为答案。
- 在已排序的矩阵中寻找最 K 小的元素这一系列的题目有:第 373 题,第 378 题,第 668 题,第 719 题,第 786 题。