# LeetCode Solution, Easy, 88. Merge Sorted Array # [88. Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array/) ## 題目敘述 You are given two integer arrays `nums1` and `nums2`, sorted in **non-decreasing order**, and two integers `m` and `n`, representing the number of elements in `nums1` and `nums2` respectively. **Merge** `nums1` and `nums2` into a single array sorted in **non-decreasing order**. The final sorted array should not be returned by the function, but instead be _stored inside the array_ `nums1`. To accommodate this, `nums1` has a length of `m + n`, where the first `m` elements denote the elements that should be merged, and the last `n` elements are set to `0` and should be ignored. `nums2` has a length of `n`. **Example 1:** Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1. **Example 2:** Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Explanation: The arrays we are merging are [1] and []. The result of the merge is [1]. **Example 3:** Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1] Explanation: The arrays we are merging are [] and [1]. The result of the merge is [1]. Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1. **Constraints:** - `nums1.length == m + n` - `nums2.length == n` - `0 <= m, n <= 200` - `1 <= m + n <= 200` - `-10**9 <= nums1[i], nums2[j] <= 10**9` **Follow up:** Can you come up with an algorithm that runs in `O(m + n)` time? ### 題目翻譯 給定兩個整數陣列 `nums1` 和 `nums2`，其中這兩個陣列的元素是以升冪排列。另外分別在給兩個整數參數 `m` 和 `n`，代表分別從 `nums1` 和 `nums2` 取出的元素數量。將 `m` 和 `n` 個元素統一編輯到 `nums1` 中，並且依照升冪排序。不需要回傳值。所以最後 `nums1` 應該會要 `m + n` 的長度。 另外思考看看如何將時間複雜度做到 `O(m + n)` ## 解法解析 這題有三種解法，第一種就是很直覺的方式，將兩者先相加後再做排序。這種方式就基本上依靠程式語言內建支援的函數來做排序處理。 Time complexity：`O((n+m)log(n+m))` Space complexity：`O(n)` 剩下兩種方式，因為兩著陣列是已經排序過的，所以利用此條件下，使用 Three Pointers 的解法，其差異只是分別從頭開始遍歷還是從尾部開始遍歷。 Three Pointers 分別指向：`m` 的數量、`n` 的數量、要插入 `nums1` 目前的索引位置。這兩種方式都能達到時間複雜度 `O(m+n)`，但是從頭開始的話，空間複雜度會是 `O(m)`，從尾部的空間複雜度則是 `O(1)`。 ### 解法範例 #### Go ##### Merge then sort ```go func merge(nums1 []int, m int, nums2 []int, n int) { for i := 0; i < n; i++ { nums1[m+i] = nums2[i] } sort.Ints(nums1) } ``` ##### Three Pointers (Start From the Beginning) ```go func merge(nums1 []int, m int, nums2 []int, n int) { nums1Copy := make([]int, m) copy(nums1Copy, nums1) var p1, p2 int = 0, 0 for p := 0; p < n+m; p++ { if p2 >= n || (p1 < m && nums1Copy[p1] <= nums2[p2]) { nums1[p] = nums1Copy[p1] p1++ } else { nums1[p] = nums2[p2] p2++ } } } ``` ##### Three Pointers (Start From the End) ```go func merge(nums1 []int, m int, nums2 []int, n int) { var p1, p2 int = m - 1, n - 1 for i := n + m - 1; i >= 0; i-- { if p2 < 0 { break } if p1 >= 0 && nums1[p1] > nums2[p2] { nums1[i] = nums1[p1] p1-- } else { nums1[i] = nums2[p2] p2-- } } } ``` #### JavaScript ##### Merge then sort ```javascript /** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */ var merge = function (nums1, m, nums2, n) { for (let i = 0; i < n; i++) { nums1[i + m] = nums2[i]; } return nums1.sort((a, b) => a - b); }; ``` ##### Three Pointers (Start From the Beginning) ```javascript /** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */ var merge = function (nums1, m, nums2, n) { const nums1Copy = nums1.slice(0, m); let p1 = 0, p2 = 0; for (let i = 0; i < m + n; i++) { if (p2 >= n || (p1 < m && nums1Copy[p1] <= nums2[p2])) { nums1[i] = nums1Copy[p1]; p1++; } else { nums1[i] = nums2[p2]; p2++; } } }; ``` ##### Three Pointers (Start From the End) ```javascript /** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */ var merge = function (nums1, m, nums2, n) { let p1 = m - 1, p2 = n - 1; for (let i = n + m - 1; i >= 0; i--) { if (p2 < 0) { break; } if (p1 >= 0 && nums1[p1] > nums2[p2]) { nums1[i] = nums1[p1]; p1--; } else { nums1[i] = nums2[p2]; p2--; } } }; ``` #### Kotlin ```kotlin ``` #### PHP ```php ``` #### Python ##### Merge then sort ```python class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ # Write the elements of num2 into the end of nums1. for i in range(n): nums1[i + m] = nums2[i] # Sort nums1 list in-place. nums1.sort() ``` ##### Three Pointers (Start From the Beginning) ```python class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ # Make a copy of the first m elements of nums1. nums1_copy = nums1[:m] # Read pointers for nums1Copy and nums2 respectively. p1 = 0 p2 = 0 # Compare elements from nums1Copy and nums2 and write the smallest to nums1. for p in range(n + m): # We also need to ensure that p1 and p2 aren't over the boundaries # of their respective arrays. if p2 >= n or (p1 < m and nums1_copy[p1] <= nums2[p2]): nums1[p] = nums1_copy[p1] p1 += 1 else: nums1[p] = nums2[p2] p2 += 1 ``` ##### Three Pointers (Start From the End) ```python class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ # Set p1 and p2 to point to the end of their respective arrays. p1 = m - 1 p2 = n - 1 # And move p backwards through the array, each time writing # the smallest value pointed at by p1 or p2. for p in range(n + m - 1, -1, -1): if p2 < 0: break if p1 >= 0 and nums1[p1] > nums2[p2]: nums1[p] = nums1[p1] p1 -= 1 else: nums1[p] = nums2[p2] p2 -= 1 ``` #### Rust ```rust ``` #### Swift ```swift ```