我来交作业了，如果数组有序的解法，不知道还能不能优化
来源：4-2 map的使用 Intersection of Two Arrays II
weixin_慕村1119904
2022-03-03
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int [] conn = new int [nums1.length + nums2.length];
int index = 0, index1 = 0, index2 = 0;
while(index1 < nums1.length && index2 < nums2.length){
if(nums1[index1] < nums2[index2]){
index1++;
}else if(nums1[index1] > nums2[index2]){
index2++;
}else{
conn[index++] = nums1[index1];
index1++;
index2++;
}
}
return Arrays.copyOfRange(conn,0,index);
}
}
写回答
1回答
-
liuyubobobo
2022-03-04
大赞，一点儿毛病都没有！：）
一个小优化是，conn 的大小不需要开成 nums1.length + nums2.length 这么大，
开 Math.min(nums1.length, nums2.length) 这么大就够了。想想为什么？
==========
更进一步，如果问题允许我们修改 nums1 或者 nums2 数组的话，conn 这个数组的空间都不需要，直接复用 nums1 或者 nums2 就好了。可以参考下面的代码。
class Solution { public int[] intersect(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int index = 0, index1 = 0, index2 = 0; while(index1 < nums1.length && index2 < nums2.length){ if(nums1[index1] < nums2[index2]){ index1++; }else if(nums1[index1] > nums2[index2]){ index2++; }else{ nums1[index++] = nums1[index1]; index1++; index2++; } } return Arrays.copyOfRange(nums1,0,index); } }但是这些优化都是常数级别的优化，尤其是复用 nums1 或者 nums2 的空间，在实际工程项目中由于破坏了传来的参数，所以可能是不被允许的。在实际面试中，应该询问面试官是否可以破坏传来的参数。
继续加油！：）
112022-03-04
相似问题