88.合并两个有序数组

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

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

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

1. 第一眼看这道题，要么空间O(m)时间O(m+n)，要么空间(1)时间O(mn)。前者跟合并有序链表差不多，后者直接插入排序。
2. 当数组从前往后遍历行不通时，不妨试试从后往前遍历。这无疑也增加了一种思考角度，就是遍历方向的问题。本题中两个数组分别从尾部开始向前相互比较，依次就可以确定合并后数组第一大,第二大,第三大...元素的位置。反过来想，实际上从前往后遍历也是可以的，前往后遍历的话可以依次可以确定合并后数组第一小,第二小,第三小...元素，需要注意的时，当将其从0索引下标开始填入nums1数组时，如果填入位置是还没确定对应元素的，那么这时候问题来了，这个冲突的元素放在哪？如果放在nums1后面为0的位置就会破坏nums1未确定数组有序的结构。因此如果要从前往后遍历的话，需要先做一步处理，就是把nums1前m个待排序元素移到nums1中的后m个位置，这样子就不必考虑放在nums1前面的冲突问题。
3. 根据2的分析，其实是一个大小为m的滑动窗口问题。

 public void merge(int[] nums1, int m, int[] nums2, int n) {
                int m1=m-1,m2=n-1;
                while(m1>=0&&m2>=0)
                {
                    if(nums1[m1]>nums2[m2])
                    {
                        nums1[m1+m2+1]=nums1[m1];
                        m1--;
                    }
                    else
                    {
                        nums1[m1+m2+1]=nums2[m2];
                        m2--;
                    }
                }
                if(m1<0)
                {
                    for(int i=0;i<=m2;i++)
                    nums1[i]=nums2[i];
                }
    }