Merge Sorted Array

题目说明

给定两组非递减的整数阵列 nums1 和 nums2，其元素个数分别为 m 和 n，长度为 m+n 和 n。
需合併两阵列至 nums1 并维持递增排序。
不需要回传值，将合併后答案填入 nums1(长度为 m+n，预留空间补0)，即不希望应用到额外的空间。

範例

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.

限制条件和特别需求

nums1.length == m + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-109 <= nums1[i], nums2[j] <= 109
Follow up: Can you come up with an algorithm that runs in O(m + n) time?

思路

一开始直觉想把 nums2 的值塞到 nums1 里，既然都已经升序排列那就只要比对 nums1 的前后值并塞进去就可以吧，但这样遇到后面补0的时候会需要再多很多判断避免问题，也造成多出额外空间事后要删掉，这想法行不通!!!那还有没有其他作法呢?

后来发现其实题目已经给了很多线索，已预留的空间和排序好的递增数列。利用上述特性可以分别从后面两两比对值，将较大的值填到 nums1 的最后面，较小的值则继续与另一个值比对，直到 nums1 被填完即比对完毕，并且没有任何值有被覆盖掉的问题。

根据此方向，有三个状况要解决

m=0,即把所有的 nums2 依序填到 nums1n=0，即 nums1 目前就是答案，不需额外做事m, n !=0，即需要由后往前各自比对，并将较大的数放入 nums1 的最后面

C++ 程式码

class Solution {public:    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {                      for (int i=m+n-1; i>-1; i--) {            if (m==0) {                nums1[i] = nums2[n-1];                n--;                continue;            }                    if (n==0)                break;                        if (nums1[m-1] <= nums2[n-1]) {                nums1[i] = nums2[n-1];                n--;            }            else {                nums1[i] = nums1[m-1];                m--;            }        }    }};

Python3 程式码

class Solution:    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:            for i in range(m+n-1, -1, -1):            if(m==0):                nums1[i] = nums2[n-1]                n = n-1                continue            if(n==0):                break                            if(nums1[m-1] <= nums2[n-1]):                nums1[i] = nums2[n-1]                n = n-1            else:                nums1[i] = nums1[m-1]                m = m-1