88. 合并两个有序数组 (Swift版本)

题目

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

提示

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109

解答

方法1: 合并后使用系统方法 sort() (最简单, 最直接)

Show Code

class Solution {
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
    	// range operator (区间运算符/区间操作符)
        for idx in 0..<n {
            nums1[m + idx] = nums2[idx]
        }
        // 闭包表达式的简短方式
        nums1.sort(by: <)
    }
}

复杂度分析

时间复杂度：O((m+n)log(m+n))

排序序列长度为 m+n，套用 sort 方法的时间复杂度即可，平均情况为 O((m+n)log⁡(m+n))
空间复杂度: O(m+n)

排序序列长度为 m+n，套用sort 方法的空间复杂度即可，平均情况为 O(m+n)

Swift 的内置排序算法 sort() 在 Swift5 之后采用了 TimSort，相较于之前的 Introsort 更 stability, 什么是 stability？它是_一种排序后维持相等元素的原始顺序的能力_, 关于 Swift 中 sort() 的 stability, 可以参考 Is sort() stable in Swift 5?

TimSort 是一种混合算法，包含插入排序O(n^2) 和 归并排序O(nlogn)，因为插入和归并都是 stability，所以 TimSort 也是

TimSort 核心原理是 切割 + 合并, 具体实现可参考 TimSort

TimSort 的平均时间复杂度为O(nlogn) ，最好情况O(n) ，最差情况O(nlogn) 。空间复杂度O(n) ，是一个稳定的排序算法。自该算法被发明以来，已被Python、Java、Android 平台和GNU Octave 用作默认排序算法。

执行用时&内存消耗

在这里插入图片描述

方法2: 双指针

方法一没有利用数组 nums1 与 nums2 已经被排序的性质。为了利用这一性质，我们可以使用双指针方法。这一方法将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。

Show code

    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        var p1 = 0, p2 = 0
        var sorted = [Int]()
        while p1 < m || p2 < n {
            if p1 == m {
                sorted.append(nums2[p2])
                p2 += 1
                // 很重要, 没有则会向下执行, 最终Crash -> Fatal error: Index out of range
                continue
            }
            if p2 == n {
                sorted.append(nums1[p1])
                p1 += 1
                // 很重要, 没有则会向下执行, 最终Crash -> Fatal error: Index out of range
                continue
            }
            if nums1[p1] < nums2[p2] {
                sorted.append(nums1[p1])
                p1 += 1
            } else {
                sorted.append(nums2[p2])
                p2 += 1
            }
        }
        for idx in 0..<(m+n) {
            nums1[idx] = sorted[idx]
        }
    }

复杂度分析

时间复杂度: O(m + n)

指针移动单调递增，最多移动 m+n 次，因此时间复杂度为 O(m+n)
空间复杂度: O(m + n)

需要建立长度为 m+n 的中间数组 sorted

方法3: 逆向双指针

方法二中，之所以要使用临时变量，是因为如果直接合并到数组 nums1 中，nums1 中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖 nums1 中的元素呢？观察可知，nums1 的后半部分是空的，可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历，每次取两者之中的较大者放进 nums1 的最后面。

严格来说，在此遍历过程中的任意一个时刻，nums1 数组中有 m−p1−1 个元素被放入 nums1 的后半部，nums2 数组中有 n−p2−1 个元素被放入 nums1 的后半部，而在指针 p1 的后面，nums1 数组有 m+n−p1−1 个位置。由于

m+n−p1−1≥m−p1−1+n−p2−1

等价于

p2≥−1

永远成立，因此 p1 后面的位置永远足够容纳被插入的元素，不会产生 p1 的元素被覆盖的情况。

Show code

    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        var p1 = m - 1, p2 = n - 1
        var tail = m + n - 1
        while p1 > -1 || p2 > -1 {
            if p1 == -1 {
                nums1[tail] = nums2[p2]
                tail -= 1
                p2 -= 1
                continue
            }
            if p2 == -1 {
                nums1[tail] = nums1[p1]
                tail -= 1
                p1 -= 1
                continue
            }
            if nums1[p1] > nums2[p2] {
                nums1[tail] = nums1[p1]
                p1 -= 1
                tail -= 1
            } else {
                nums1[tail] = nums2[p2]
                p2 -= 1
                tail -= 1
            }
        }
    }