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

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

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

简单地说,预期的结果应该是：

[1,2,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,38]

这是完全可行的.

但是,我的问题是：

如果我们尝试使用更“Swifty”的短缺解决方案来实现它会是什么？

请注意,这样做：

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

不会那么聪明,因为它应该以O(n)来完成.

我试图在函数式编程中解决你的问题而没有变量.

给出2个阵列

let nums0 = [1,38]
let nums1 = [2,31]

我们将第一个与第二个版本的反转版本连接起来

let all = nums0 + nums1.reversed()

结果将是这种金字塔.

[1,38,2]

理论

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

[1,2] -> we pick 1 (left edge)
[7,2] -> we pick 2 (right edge)
[7,5] -> we pick 5 (right edge)
[7,17] -> we pick 7 (left edge)
[17,17] -> we pick 17 (right edge)
[17,29] -> we pick 17 (left edge)
[25,29] -> we pick 25 (left edge)
[38,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,5]
We selected 7: [1,7]
We selected 17: [1,17]
We selected 17: [1,17]
We selected 25: [1,25]
We selected 29: [1,29]
We selected 31: [1,31]
We selected 38: [1,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.
我们传递给reduce一个包含all数组和一个空数组的元组.

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个元素的专有名称

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.如果第一个<最后我们需要：
>返回输入减去第一个elemewnt
> return输出第一个输入元素

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

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),因为对所有元素执行闭包

时间复杂度为O(n)^ 2.请参阅以下@dfri的有价值的评论.

版本2

这个版本应该具有O(n)时间复杂度.

let merged = all.reduce(into: (all,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

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

猜你在找的Swift相关文章