Fork me on GitHub

Find K Pairs with Smallest Sums

题目介绍

LeetCode 373. Find K Pairs with Smallest Sums,题目的意思给定两个升序排序整数数组,从两个数组中各取一个数字组合成 (u,v),输出前 k 个最小的组合。

解题思路

我原本想定义一套判断规则,但是发现要处理很多下标情况。后来看了 Discuss 之后,最好的方式是定义 Heap(堆数据结构),但是 Swift 中不包含这样的数据结构。退而求其次,用了一个方法,记录 nums1 中每个元素已经配对到 nums2 中的第几个,每次遍历 nums1 中的元素,求出 nums1[i]+nums2[index[i]],取出最小值放入输出数组中即可。

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
class Solution {
func kSmallestPairs(_ nums1: [Int], _ nums2: [Int], _ k: Int) -> [[Int]] {
if k <= 0 || nums1.isEmpty || nums2.isEmpty {
return []
}
let cnt = min(k, nums1.count * nums2.count)
var index = Array(repeatElement(0, count: nums1.count))
var pairs: [[Int]] = []
var n = 0
while n < cnt {
var min = Int.max
var m = 0
for i in 0..<nums1.count {
if index[i] < nums2.count && nums1[i]+nums2[index[i]] < min {
min = nums1[i]+nums2[index[i]]
m = i
}
}
pairs.append([nums1[m], nums2[index[m]]])
index[m] += 1
n += 1
}
return pairs
}
}

版权声明



Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于Ivan’s Blog | 叶帆的博客博客( http://yeziahehe.com ),版权所有,侵权必究。

本文链接:http://yeziahehe.com/2017/11/05/FindKPairsWithSmallestSums/