题目描述

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。

所以永远不存在元素被覆盖的情况