[LeetCode]Merge Sorted Array

Question
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.

本题难度Easy。

【题意】
把nums1和nums2合并放入nums1中。

【复杂度】
时间 O(N) 空间 O(N)

【思路】
有时候思路变一变就有新发现。一开始我是希望从左往右进行读取比较再放入nums1，但是问题是会对nums1的原有值产生影响。

关键就在于读取顺序！如果从右往左读取就不会影响到nums1。利用三个指针：i1标记nums1，i2标记nums2，index标记总进度。然后看​​nums1[i1]​​​与​​nums2[i2]​​哪个大哪个放到index那儿。有没有比较完毕的标志是i2<0。（行6）因为我们要把nums2全部搬到nums1才告结束。如果i1读到头了nums2还没搬完，那就说明nums2剩下的可以整体搬到sum1了。

【代码】

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //require
        int i1=m-1,i2=n-1,index=m+n-1;
        //invariant
        while(i2>=0){
            if(i1>=0){
                if(nums1[i1]<nums2[i2])
                    nums1[index--]=nums2[i2--];
                else
                    nums1[index--]=nums1[i1--];
            }else
                nums1[index--]=nums2[i2--];
        }
    }
}