关于leetcode88题的一个小问题

来源:3-5 三路快排partition思路的应用 Sort Color

v不离不弃v

2020-02-16

波波老师您好,关于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里面?这样是不是错了?

写回答

1回答

liuyubobobo

2020-02-16

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


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


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


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


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


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


继续加油!:)

0
4
liuyubobobo
回复
v不离不弃v
谁都有痛苦的过程,熬过去就好了。功夫不负有心人,加油!:)
2020-02-16
共4条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7410 学习 · 1150 问题

查看课程