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]]，取出最小值放入输出数组中即可。

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/