关于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 做的事情。
如果你认为这个算法有问题,可以尝试根据自己的思考,构造一个测试用例,然后实际用这个代码运行一遍,看看结果是不是真的出问题了?
如果没有出问题,可以使用单步跟踪的方式具体看一看,算法为什么能得到正确的结果,自己认为会出现错误的地方,实际上算法为什么没有出现错误?自己的思维哪里错了?
进步就发生在这个过程中哦。
继续加油!:)
042020-02-16
相似问题
回答 1
回答 1