题目：合并已排序数组
难度：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的位置。
我的代码：
public void merge(int[] nums1, int m, int[] nums2, int n) {
int j = m - 1;
for (int i = 0; i < n; i++) {
if (j == -1 || nums2[i] >= nums1[j] ) {
while (i < n) {
nums1[++j] = nums2[i++];
}
return;
} else {
int k = j;
for (; k > -1 && nums1[k] > nums2[i]; k--) {
nums1[k+1] = nums1[k];
}
nums1[k+1] = nums2[i];
j++;
}
}
}
我的复杂度：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++
答案代码：
public void merge(int A[], int m, int B[], int n) {
int i = m-1, j = n-1, k = m+n-1;
while (i>-1 && j>-1)
A[k--] = A[i] > B[j] ? A[i--] : B[j--];
while (j>-1)
A[k--] = B[j--];
}
答案思路：
既然从前往后会覆盖到，但是后面全是0，那么从后往前就不会覆盖到了。
（就算极端情况，A内全部小于B，后面的0刚好够B放，不会出现覆盖情况）
1、当 i 且 j 都没消耗完时，从后往前，谁大谁就入，并且相应指针消耗1；
2、如果 j 还没消耗完，则将B内剩下的都放入A；（此时如果A没消耗完也不需要管了，因为本来就已经在A里面按顺序排好了）