[Swift]LeetCode88. 合并两个有序数组 | Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.
• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

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

Output: [1,2,2,3,5,6]

---

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

说明:

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

示例:

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

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

---

8ms

class Solution {
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        var index1 = 0
        var index2 = 0
        
        while index2 < n {
            if nums1[index1] > nums2[index2] || index1-index2 >= m {
                nums1.insert(nums2[index2], at: index1)
                index1 += 1
                index2 += 1
            } else if nums1[index1] <= nums2[index2] {
                index1 += 1
            }
        }
    }
}

---

12ms

/**
 * 思路：从尾部开始合并，避免覆盖
 * 时间复杂度：O(n)，空间复杂度：O(1)
 */
class Solution {
    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
            }
        }
    }
}

---

 16ms

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

---

16ms

class Solution {
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        var i = 0, j = 0
        
        while j < n && i < nums1.count {
            if (nums1[i] < nums2[j] && i < m + j) {
                i += 1
            } else {
                nums1.insert(nums2[j], at: i)
                i += 1
                j += 1
            }
        }
        if nums1.count > n + m {
            nums1.removeLast(nums1.count - n - m)
        }
    }
}

---

20ms

class Solution {
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        
        for i in m..<m+n {
            nums1[i] = nums2[i-m]
        }
        nums1 = nums1.sorted()
    }
}

---

 20ms

class Solution {
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        guard m > 0 else {
            nums1 = nums2
            return
        }
        
        guard n > 0 else {
            return
        }
        
        var i = 0
        var j = 0
        
        var mergedNums = Array(nums1[..<m])
        print("MergedNums: \(mergedNums)")
        
        while i < mergedNums.count && j < n {
            if nums2[j] <= mergedNums[i] {
                mergedNums.insert(nums2[j], at: i)
                j += 1
            } else {
                i += 1
            }
        }
        
        if j < n {
            mergedNums += nums2[j..<n]
        }
        
        nums1 = mergedNums
    }
}

---

32ms

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

---

36ms

class Solution {
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        var sArr = ArraySlice<Int>()
        if m != 0 && m<=nums1.count {
           sArr = nums1[0...(m-1)]
        }
        if n != 0 && n <= nums2.count  {
            sArr.append(contentsOf: nums2[0...(n-1)])
        }
        nums1.removeAll()
        nums1.append(contentsOf: sArr)
        nums1.sort { (x, y) -> Bool in
            return x < y
        }  
    }
}

---

40ms

class Solution {
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        
        for i in 0..<nums2.count{
        
            nums1[m+i]=nums2[i]
        }
        
        
        nums1 = quickSort(data:nums1)
        
    }
   func quickSort(data:[Int])->[Int]{
        if data.count<=1 {
            return data
        }
        
        var left:[Int] = []
        var right:[Int] = []
        let pivot:Int = data[data.count-1]
        for index in 0..<data.count-1 {
            if data[index] < pivot {
                left.append(data[index])
            }else{
                right.append(data[index])
            }
        }
        
        var result = quickSort(data: left)
        result.append(pivot)
        let rightResult = quickSort(data: right)
        result.append(contentsOf: rightResult)
        return result
    }
}