关于leetcode88题的一个小问题

Question

波波老师您好，关于leetcode88题，合并2个数组，他题目的要求是可以假设nums1的空间是>=nums1+nums2的，但是我当时做的时候，是按照nums1的空间=nums1+nums2的，然后AC了，代码如下，我使用从后往前遍历的：

public class Solution1 {
	public void merge(int[] nums1, int m, int[] nums2, int n) {
		int l=m-1;
		int r=n-1;
		for(int i=m+n-1;i>=0;i--) {
			if(l<0) {
				nums1[i]=nums2[r];r--;
			}
			else if(r<0) {
				nums1[i]=nums1[l];l--;
			}
			else if(nums1[l]<=nums2[r]) {
				nums1[i]=nums2[r];r--;
			}
			else{
				nums1[i]=nums1[l];l--;
			}
		}
	}
}

我不知道这个行不行，到底需要不需要考虑nums1的空间大于2个数组空间之和的情况。

下面是官方给的题解:

class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    // two get pointers for nums1 and nums2
    int p1 = m - 1;
    int p2 = n - 1;
    // set pointer for nums1
    int p = m + n - 1;

    // while there are still elements to compare
    while ((p1 >= 0) && (p2 >= 0))
      // compare two elements from nums1 and nums2 
      // and add the largest one in nums1 
      nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];

    // add missing elements from nums2
    System.arraycopy(nums2, 0, nums1, 0, p2 + 1);//这里有些不懂
  }
}

最后一行代码有些不理解，这个难道没有忽略当nums2提前遍历完（已经在nums1中填充并排好序,但是nums1此时指针还未到0）之后，需要将nums1自己本身复制到nums1的原来的地方吗？按照我的理解就是，无论是nums1还是nums2有没有遍历完，最后都是将nums2没有遍历完的地方复制到nums1里面？这样是不是错了？

Answer 1

liuyubobobo 2020-02-16 09:12:40

我不确定我有没有正确理解你的问题。

如果 nums1 没有遍历完，，反正我们最后的结果是放在 nums1 中的，说明没有遍历完的那些 nums1 的元素都小于 nums2 的元素，那么他们就应该放在那里，不用动了。

最后要处理的，是 nums2 没有遍历完的情况，就是那句 arraycopy 做的事情。

如果你认为这个算法有问题，可以尝试根据自己的思考，构造一个测试用例，然后实际用这个代码运行一遍，看看结果是不是真的出问题了？

如果没有出问题，可以使用单步跟踪的方式具体看一看，算法为什么能得到正确的结果，自己认为会出现错误的地方，实际上算法为什么没有出现错误？自己的思维哪里错了？

进步就发生在这个过程中哦。

继续加油！：）

• 提问者 v不离不弃v #1

  System.arraycopy(nums2, 0, nums1, 0, p2 + 1);波波老师，如果nums2已经遍历完了，即这个时候p2=-1；此时如果再次copy是不是就不会copy了，因为length=0？对吗，如果这样的话我就懂了，还有波波老师，前面第一个程序是我自己写的，但是我只考虑到nums1的空间=nums1+nums2的空间的情况，请问需要考虑nums1空间>nums2+nums1空间的情况吗？我觉得答案也没有考虑到这种情况。。。

• liuyubobobo 回复 提问者 v不离不弃v #2

  1 对。2 你的程序只要 >= nums1 + nums2 就没问题。因为有效数据在 nums1 + nums2 范围里的，即使  >nums2+nums1，多余的元素也没有动。你给出的解答程序也是如此。

• 提问者 v不离不弃v 回复 liuyubobobo #3

  好的谢谢波波老师，刷题虽然痛苦但是也很有趣，就是一直想着怎么在美国找到工作真痛苦。。。我是0基础转CS，剩的时间也不多了，哎，现在除了刷题&上课，其他啥事也没心情，那也不想去，看着其他准备毕业回国的同学天天玩就羡慕，哎。。。。波波老师好羡慕你们在美国找到工作证明自己的人。。

点开查看后面1条评论