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

考虑以下两个排序的数组:

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 

因此:

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


这是完全可行的.

但是,我的问题是:

如果我们试图通过更多"Swifty"缺乏解决方案来实现它,会是什么样的？



请注意,这样做:

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


不会那么聪明,因为应该这样做O(n).


1> Luca Angelet..：
我试图在功能编程中解决你的问题而没有变量.

给出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 

它是如何工作的？

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 我们需要:



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


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

if first 

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 

        
抱歉回复晚了。Imo，O（n）^ 2和O（m + n）^ 2是相同的-我什至认为后者是Big-O符号的（常见）误用。我们可以不失一般性地假设&＃39;n> m&＃39;，然后对大小为&＃39;2n&＃39;的输入数组执行渐近分析，在这种情况下，&＃39;2&＃39;只是一个常数，并且对渐近增长没有影响Big-O分析（因为我们省略了最终表示法中的任何常量：例如，不编写（`O（3n）`，而是`O（n）`）。因此摘要：我将时间复杂度视为`O（ n）^ 2`，由于复制。