Swift 3.0
//
// E_88_MergeSortedArray.swift
// AlgorithmLeetCode
//
// Created by okerivy on 2017/3/8.
// Copyright © 2017年 okerivy. All rights reserved.
// https://leetcode.com/problems/merge-sorted-array
import Foundation
// MARK: - 题目名称: 88. Merge Sorted Array
/* MARK: - 所属类别:
标签: Array, Two Pointers
相关题目:
(E) Merge Two Sorted Lists
*/
/* MARK: - 题目英文:
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.
*/
/* MARK: - 题目翻译:
给定两个排好顺序的整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，并使得 nums1 成为一个有序数组。
注意：
你可以认为 nums1 有足够的空间(大于或等于m + n)来存储 nums2 中的元素。数组 nums1 和 nums2 初始化的元素数量分别 m 和 n。
因为本题有 in-place 的限制，故必须从数组末尾的两个元素开始比较；否则就会产生挪动，一旦挪动就会是 O(n2) 的。
自尾部向首部逐个比较两个数组内的元素，取较大的置于数组 A 中。
由于 A 的容量较 B 大，故最后 m == 0 或者 n == 0 时仅需处理 B 中的元素，因为 A 中的元素已经在 A 中，无需处理。
*/
/* MARK: - 解题思路:
A和B都已经是排好序的数组，我们只需要从后往前比较就可以了。
因为A有足够的空间容纳A + B，我们使用游标i指向m + n - 1，也就是最大数值存放的地方，从后往前遍历A，B，谁大就放到i这里，同时递减i。
*/
/* MARK: - 复杂度分析:
最坏情况下需要遍历两个数组中所有元素，时间复杂度为 O(n). 空间复杂度 O(1).
*/
// MARK: - 代码:
private class Solution {
func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
// 游标 记录待插入位置
var last = m + n - 1
// 记录 num1 待比较的位置
var index1 = m - 1
// 记录 num2 待比较的位置
var index2 = n - 1
// 如果插入的位置一直有空位,就继续循环
while last >= 0 {
// 如果两个数组都还没有比较完成
if index1 >= 0 && index2 >= 0 {
// 如果nums1 的元素大于 nums2 的元素, 那么就把nums1 的元素插入游标所在的位置
if nums1[index1] >= nums2[index2] {
nums1[last] = nums1[index1]
index1 -= 1
} else {
nums1[last] = nums2[index2]
index2 -= 1
}
// nums2 数组已经比较完成, 只剩下 num1了
} else if index1 >= 0 {
nums1[last] = nums1[index1]
index1 -= 1
// nums1 数组已经比较完成 只剩下 num2了
} else if index2 >= 0 {
nums1[last] = nums2[index2]
index2 -= 1
}
// 游标指向前一个位置
last -= 1
}
}
}
// MARK: - 测试代码:
func mergeSortedArray() {
var nums1 = [2, 4, 5, 7, 10]
let m = nums1.count
let nums2 = [1, 3, 3, 4, 5, 8,9,9]
let n = nums2.count
// 先增加 nums1的数组长度,方便插入nums2的数据
for _ in 0 ..< n {
nums1.append(0)
}
Solution().merge(&nums1, m, nums2, n)
print(nums1)
}
