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: - 題目翻譯:
 
 給定兩個排好順序的整數(shù)數(shù)組 nums1 和 nums2苗沧，將 nums2 合并到 nums1 中竭贩，并使得 nums1 成為一個有序數(shù)組围苫。
 注意：
 你可以認為 nums1 有足夠的空間(大于或等于m + n)來存儲 nums2 中的元素。數(shù)組 nums1 和 nums2 初始化的元素數(shù)量分別 m 和 n状飞。

 
 因為本題有 in-place 的限制，故必須從數(shù)組末尾的兩個元素開始比較；否則就會產(chǎn)生挪動福扬，一旦挪動就會是 O(n?2) 的茵瀑。 
 自尾部向首部逐個比較兩個數(shù)組內(nèi)的元素间驮，取較大的置于數(shù)組 A 中。
 由于 A 的容量較 B 大马昨，故最后 m == 0 或者 n == 0 時僅需處理 B 中的元素竞帽，因為 A 中的元素已經(jīng)在 A 中，無需處理鸿捧。
 
 */



/* MARK: - 解題思路:
 
 A和B都已經(jīng)是排好序的數(shù)組屹篓，我們只需要從后往前比較就可以了。
 
 因為A有足夠的空間容納A + B匙奴，我們使用游標i指向m + n - 1堆巧，也就是最大數(shù)值存放的地方，從后往前遍歷A，B谍肤，誰大就放到i這里啦租，同時遞減i。
 
 */


/* MARK: - 復雜度分析:
 
 最壞情況下需要遍歷兩個數(shù)組中所有元素荒揣，時間復雜度為 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
        
        // 如果插入的位置一直有空位,就繼續(xù)循環(huán)
        while last >= 0 {
            
            // 如果兩個數(shù)組都還沒有比較完成
            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 數(shù)組已經(jīng)比較完成, 只剩下 num1了
            } else if index1 >= 0 {
                nums1[last] = nums1[index1]
                index1 -= 1
                
                // nums1 數(shù)組已經(jīng)比較完成 只剩下 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的數(shù)組長度,方便插入nums2的數(shù)據(jù)
    for _ in 0 ..< n {
        nums1.append(0)
    }
    
    Solution().merge(&nums1, m, nums2, n)
    
    print(nums1)
}