Merge Sorted Array 合并两个有序数组

问题描述：

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

$nums1.length == m + n\\ nums2.length == n\\ 0 <= m, n <= 200\\ 1 <= m + n <= 200\\ -10^9 <= nums1[i], nums2[j] <= 10^9$

分析

常见的处理方式，就不赘述了。

先说结论，从尾部进行双指针。

$n u m s 1$ 长度为 $m + n$ , $n u m 2$ 长度为 $n$ ，但是 $n u m s 1$ 中只有前m个是有效的数据。
所以定义3个指针，

p1 表示nums1中最后一个数字
p2 表示nums2中最后一个数字。
p = m+n-1,表示nums1中可以放入数字的位置。

整个过程可以看成是一个逆向的归并。
注意指针的移动，别越界，当一个指针小于0时，就可以单独处理另一个指针。

代码

Sort

public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m-1,p2 = n-1,idx = m+n-1;
        while( idx>=0 ){
            if(p1>=0&&p2>=0){
                if(nums2[p2]>=nums1[p1]){
                    nums1[idx--] = nums2[p2--];
                }
                else{
                    nums1[idx--] = nums1[p1--];
                }
            }
            else if(p1>=0){
                nums1[idx--] = nums1[p1--];
            }
            else{
                nums1[idx--] = nums2[p2--];
            }
        }
        return;
    }