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
inputand the second oneoutput.
Step by step the reduce will remove the minimum element from the edges ofinputwill append it tooutput.
然后,在闭包内部,我们给出了元组的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
inputwill 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
