arrays - 如何在 Swift 中合并两个排序数组？

Question

考虑以下两个排序数组:

let arr1 = [1, 7, 17, 25, 38]
let arr2 = [2, 5, 17, 29, 31]

简单来说，预期的结果应该是:

[1, 2, 5, 7, 17, 17, 25, 29, 31, 38]

事实上，如果我们试图对这个问题做一个简单的研究，我们会发现许多资源提供了以下“典型”方法:

func mergedArrays(_ array1: [Int], _ array2: [Int]) -> [Int] {
    var result = [Int]()
    var i = 0
    var j = 0

    while i < array1.count && j < array2.count {
        if array1[i] < array2[j] {
            result.append(array1[i])
            i += 1
        } else {
            result.append(array2[j])
            j += 1
        }
    }

    while i < array1.count {
        result.append(array1[i])
        i += 1
    }

    while j < array2.count {
        result.append(array2[j])
        j += 1
    }

    return result
}

因此:

let merged = mergedArrays(arr1, arr2) // [1, 2, 5, 7, 17, 17, 25, 29, 31, 38]

这是完全可行的。

但是，我的问题是:

如果我们尝试使用更“Swifty”的简写解决方案来实现它会怎样？

注意这样做:

let merged = Array(arr1 + arr2).sorted()

不会那么聪明，因为它应该以 O(n) 的形式完成。

Answer 1

我试图在函数式编程和不使用变量中解决您的问题。

给定 2 个数组

let nums0 = [1, 7, 17, 25, 38]
let nums1 = [2, 5, 17, 29, 31]

我们将第一个与第二个的反向版本连接

let all = nums0 + nums1.reversed()

结果就是这种金字塔。

[1, 7, 17, 25, 38, 31, 29, 17, 5, 2]

理论

现在，如果我们一个接一个地选取边缘(左或右)的最小元素，我们保证会按升序选取所有元素。

[1, 7, 17, 25, 38, 31, 29, 17, 5, 2] -> we pick 1 (left edge)
[7, 17, 25, 38, 31, 29, 17, 5, 2] -> we pick 2 (right edge)
[7, 17, 25, 38, 31, 29, 17, 5] -> we pick 5 (right edge)
[7, 17, 25, 38, 31, 29, 17] -> we pick 7 (left edge)
[17, 25, 38, 31, 29, 17] -> we pick 17 (right edge)
[17, 25, 38, 31, 29] -> we pick 17 (left edge)
[25, 38, 31, 29] -> we pick 25 (left edge)
[38, 31, 29] -> we pick 29 (right edge)
[38, 31] -> we pick 31 (right edge)
[38] -> we pick 38 (both edges)

现在让我们看看我们构建的包含所有这些元素的数组。

We selected 1: [1]
We selected 2: [1, 2]
We selected 5: [1, 2, 5]
We selected 7: [1, 2, 5, 7]
We selected 17: [1, 2, 5, 7, 17]
We selected 17: [1, 2, 5, 7, 17, 17]
We selected 25: [1, 2, 5, 7, 17, 17, 25]
We selected 29: [1, 2, 5, 7, 17, 17, 25, 29]
We selected 31: [1, 2, 5, 7, 17, 17, 25, 29, 31]
We selected 38: [1, 2, 5, 7, 17, 17, 25, 29, 31, 38]

这看起来像我们想要实现的结果吧？

现在是时候编写一些 Swifty 代码了。

代码!

好的，我们如何在函数式编程中做到这一点？

这是代码

let merged = all.reduce((all, [Int]())) { (result, elm) -> ([Int], [Int]) in

    let input = result.0
    let output = result.1

    let first = input.first!
    let last = input.last!
    // I know these ☝️ force unwraps are scary but input will never be empty

    if first < last {
        return (Array(input.dropFirst()), output + [first])
    } else {
        return (Array(input.dropLast()), output + [last])
    }

}.1

它是如何工作的？

1. 我们将包含 all 的元组传递给 reduce数组和一个空数组。

all.reduce((all, [Int]()))

We will call first array input and the second one output. Step by step the reduce will remove the minimum element from the edges of input will append it to output.

2. 然后，在闭包内部，我们为 out 元组的 2 个元素赋予适当的名称

let input = result.0
let output = result.1

3.我们选择输入的第一个和最后一个元素

let first = input.first!
let last = input.last!

Yeah, I don't like force unwraps either but since input will never be empty, these force unwraps will never produce a fatal error.

4. 现在如果first < last我们需要:

• 返回输入减去第一个元素
• 返回输出+输入的第一个元素

否则我们做相反的事情。

if first < last {
    return (Array(input.dropFirst()), output + [first])
} else {
    return (Array(input.dropLast()), output + [last])
}

5. 最后，我们选择 reduce 返回的元组的第二个元素，因为它是我们存储结果的地方。

}.1  

时间复杂度

计算时间为 O(n + m)，其中 n 为 nums0.count，m 为 nums1.count，因为:

nums1.reversed()

这个☝️是O(1)

all.reduce(...) { ... }

这 ☝️ 是 O(n + m) 因为闭包是针对 all 的每个元素执行的

时间复杂度为 O(n) ^ 2。请参阅下面来自 @dfri 的宝贵评论。

版本 2

这个版本应该真的有 O(n) 的时间复杂度。

let merged = all.reduce(into: (all, [Int]())) { (result, elm) in
    let first = result.0.first!
    let last = result.0.last!

    if first < last {
        result.0.removeFirst()
        result.1.append(first)
    } else {
        result.0.removeLast()
        result.1.append(last)
    }
}.1