题目：合并已排序数组
难度：Easy
题目内容：
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
翻译：
给定两个排序的整数数组nums1和nums2，将nums2合并到nums1中作为一个排序数组。
注意:
nums1和nums2中初始化的元素数量分别为m和n。
nums1有足够的空间（大小大于或等于m+n）来容纳nums2中的额外元素。
我的思路：此处和归并排序中的小段归并有点像，不一样的地方在于在于其中nums1数组的长度是合并之后的长度。
这样一来用传统的归并排序中的合并就不行了，因为在合并过程中可能将nums1数组中的数覆盖掉（eg.【4，5，0，0】【1，2】）
除非再新建一个临时数组，将二者合并一起放入此数组中，然后再将此数组的值全部复制到nums1，那这样nums1的长度就没什么意义了。
所以可以考虑归并排序的第二种方法———插入排序。原理不再赘述。把nums2直接当作接在nums1后面的数即可。
三个指针：i 表示此时nums2的位置（从0开始）；j表示此时nums1的位置（从m-1开始）；k表示内部循环中nums1的位置。
我的代码：
1 public void merge(int[] nums1, int m, int[] nums2, int n) { 2 int j = m - 1; 3 for (int i = 0; i < n; i++) { 4 if (j == -1 || nums2[i] >= nums1[j] ) { 5 while (i < n) { 6 nums1[++j] = nums2[i++]; 7 } 8 return; 9 } else { 10 int k = j; 11 for (; k > -1 && nums1[k] > nums2[i]; k--) { 12 nums1[k+1] = nums1[k]; 13 } 14 nums1[k+1] = nums2[i]; 15 j++; 16 } 17 } 18 }
我的复杂度：O（N*M） 空间复杂度 O（1）
编码过程中的问题：
1、第4行，当m==0的时候，nums1内也是有一个0的，此时如果不加以判断，就会把0当作元素直接进入归并排序中去，然后就会越界，所以加入 j == -1 || 。
eg.【0】m=0【1】n=1。
2、第15行，忘记了此时放入了一个，nums1的指针需要向右移动一个 —— j++
答案代码：
1 public void merge(int A[], int m, int B[], int n) { 2 int i = m-1, j = n-1, k = m+n-1; 3 while (i>-1 && j>-1) 4 A[k--] = A[i] > B[j] ? A[i--] : B[j--]; 5 while (j>-1) 6 A[k--] = B[j--]; 7 }
答案思路：
既然从前往后会覆盖到，但是后面全是0，那么从后往前就不会覆盖到了。
（就算极端情况，A内全部小于B，后面的0刚好够B放，不会出现覆盖情况）
1、当 i 且 j 都没消耗完时，从后往前，谁大谁就入，并且相应指针消耗1；
2、如果 j 还没消耗完，则将B内剩下的都放入A；（此时如果A没消耗完也不需要管了，因为本来就已经在A里面按顺序排好了）