leetcode | 88. 合并两个有序数组
题目描述
88. 合并两个有序数组 
分析
题目不允许更改nums1的长度，要求原地更改。
题目其实不难，如果记住可以从后往前合并的解法，但是正向遍历的问题是什么呢？ ——元素覆盖。那为什么负向遍历就不会有这个问题呢？
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {
let i=m-1,j=n-1,p=m+n-1;
while(i>=0&&j>=0){
if(nums1[i]>nums2[j]){
nums1[p]=nums1[i];
i--;
p--;
continue;
}
nums1[p]=nums2[j];
j--;
p--;
}
while(j>=0){
nums1[p]=nums2[j];
j--;
p--;
}
return nums1;
};
为什么反向不会存在元素覆盖问题
其实就是一个数学问题。
假设，nums1=[a1,a2,…,an,0,0,…,0] nums2=[b1,b2,…,bn]; 合并过后的占据后x个，这x个，来自于k1个a串，k2个b串元素，求证m-k1+x<=n,成立。
最后，转为求证k2<=n,成立。
取等号的时候是什么场景？
就是nums1的元素所有都小于nums2，后部分刚好全部由nums2填充。
小于号呢？
x中至少含有一个元素来自nums1，那么m-k1+x<n成立，也就是，至少有一个空位是0。
所以永远不存在元素被覆盖的情况