Swift 合并两个有序数组 - LeetCode

LeetCode

题目： 合并两个有序数组

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m n）来保存 nums2 中的元素。

示例:

代码语言：javascript复制

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

方案一：

使用辅助数组，从前往后排序，空间复杂度O(n), 时间复杂度O(n)

代码一：

代码语言：javascript复制

func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
    if m == 0 {
        nums1 = nums2
    }
    
    var num = [Int]()
    var newNums1 = Array(nums1[0..<m])
    var nums2 = nums2
    while !newNums1.isEmpty && !nums2.isEmpty {
        if newNums1.first! <= nums2.first! {
            num.append(newNums1.first!)
            newNums1.removeFirst()
        } else {
            num.append(nums2.first!)
            nums2.removeFirst()
        }
        if newNums1.isEmpty {
            num.append(contentsOf: nums2)
            nums1 = num
        }
        if nums2.isEmpty {
            num.append(contentsOf: newNums1)
            nums1 = num
        }
    }
}

方案二：

从后往前排序，空间复杂度O(1),时间复杂度O(n)

代码二：

代码语言：javascript复制

func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
    var i = m - 1, j = n - 1
    while i >= 0 || j >= 0 {
        if j < 0 || (i >= 0 && nums1[i] > nums2[j]) {
            nums1[i   j   1] = nums1[i]
            i -= 1
        } else {
            nums1[i   j   1] = nums2[j]
            j -= 1
        }
    }
}

用Swift开始学习算法中，在LeetCode中开始做初级算法这一章节，将做的题目在此做个笔记，希望有更好方法同学们cue我哦。

swift

0 人点赞