如何在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数组的元组和一个空数组.

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

我们将调用第一个数组input和第二个数组output.reduce将逐步删除input将附加到其边缘的最小元素output.

2.然后,瓶盖内,我们给予适当的名字出来的元组的2种元素

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

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

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

是的,我不喜欢强行解缠,但是因为input永远不会是空的,所以这些力量展开永远不会产生致命的错误.

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

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

否则我们会做相反的事情.

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

Answer 2

我不确定你所说的“更‘Swifty’”是什么意思，但就是这样。

我会编写如下所示的函数。它不是更短，而是更通用：您可以合并任意两个Sequences，只要它们具有相同的Element类型并且Element是Comparable：

/// Merges two sequences into one where the elements are ordered according to `Comparable`.
///
/// - Precondition: the input sequences must be sorted according to `Comparable`.
func merged<S1, S2>(_ left: S1, _ right: S2) -> [S1.Element]
    where S1: Sequence, S2: Sequence, S1.Element == S2.Element, S1.Element: Comparable
{
    var leftIterator = left.makeIterator()
    var rightIterator = right.makeIterator()

    var merged: [S1.Element] = []
    merged.reserveCapacity(left.underestimatedCount + right.underestimatedCount)

    var leftElement = leftIterator.next()
    var rightElement = rightIterator.next()
    loop: while true {
        switch (leftElement, rightElement) {
        case (let l?, let r?) where l <= r:
            merged.append(l)
            leftElement = leftIterator.next()
        case (let l?, nil):
            merged.append(l)
            leftElement = leftIterator.next()
        case (_, let r?):
            merged.append(r)
            rightElement = rightIterator.next()
        case (nil, nil):
            break loop
        }
    }
    return merged
}

另一个有趣的增强功能是使序列变得惰性，即定义一个MergedSequence及其随附的迭代器结构，用于存储基本序列并根据需要生成下一个元素。这与标准库中的许多函数的作用类似，例如zipor Sequence.joined。（如果您不想定义新类型，也可以返回一个AnySequence<S1.Element>。）