88. 合并两个有序数组

双指针 · 04-03

我的思路

直接尝试赋新值给nums1=nums1[:m]+nums2,但在Leetcode的运行环境中,这样的办法行不通,只是重新绑定了一个新的列表对象,原先的nums1并没有被改变,在测试的时候后台会检查原先的nums1是否有被修改,因此这种办法是行不通的,需要在原数组上一个个修改数值才行

纠正

还是需要用双指针的思路,判断值,然后把值填进表中

初始化三个指针,分别定位在nums1(短)、nums2和nums1(长)的最后一个元素,对应的索引值分别为m-1, n-1, m+n-1,接下来依次开始判断nums1(短)和nums2的元素大小,把更大的那个放到nums1(长)的后面,这也是为什么要有第三个指针的原因,因为我们需要修改的是原始nums1

例子:nums1 = [1,2,3,0,0,0,0], m = 3, nums2 = [2,4,5,7], n = 4

思路:初始化三个指针的值分别为p = 2, q = 3, pos = 6,从左右边开始:

  1. 判断nums1[2]和nums2[3]的大小,7>3,所以把7放到nums1[6],此时已经将nums2[3]的这个元素用掉了,所以要把nums2对应的指针往左边移一位,q -= 1,变成2,p的值不变,因为这个元素还没有被安排掉,同时nums1[6]已经安排了数字进来,所以第三个指针也要往左移,pos -= 1
  2. 判断nums1[2]和nums2[2]的大小,5>3,所以把5放到nums1[5],重复上面的步骤
  3. 判断nums1[2]和nums2[0]的大小,3>2,所以把3放到nums1[3],然后p -= 1,p变为1,q仍为0,pos变为2
  4. 判断nums1[1]和nums2[0]的大小,两个数值相等,放哪一个都可以,默认把nums2的这个元素放过去,所以把2放到nums1[2],然后q -= 1,q变为-1,说明nums2的元素全部放完了,结束

反思

  1. 这题比较好的地方在于,给到的序列已经是按顺序排好了的,都是非递减数列,不需要我们再做排序操作,可以直接按顺序遍历进行比较和放置数值
  2. 需要比较巧妙处理的一个点是,在大的while循环中条件要设置为q>0,因为可能已经把nums1(短)的元素全部安排完了,但nums2还有元素,需要继续安排。一方面题目给到我们的序列已经是按非递减顺序排好了的,另一方面就算p<0了,根据我们的程序设计,这说明我们已经安排完了nums1(短)的所有元素,每个元素都已经被放置,所以此时原先nums1(短)剩下的这几个位置相当于是没用的,直接再把nums2里剩下的元素按顺序安排过来就好了

结果

0ms (100%), 17.47MB (78.94%)