题目:
给定两个数组,编写一个函数来计算它们的交集。
方法:排序+双指针
如果两个数组是有序的,则可以使用双指针的方法得到两个数组的交集。
首先对两个数组进行排序,然后使用两个指针遍历两个数组。
初始时,两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字,如果两个数字不相等,则将指向较小数字的指针右移一位,如果两个数字相等,将该数字添加到答案,并将两个指针都右移一位。当至少有一个指针超出数组范围时,遍历结束。
**return Arrays.copyOfRange(intersection, 0, index);** 主要用于对一个已有的数组进行截取复制,复制出一个**左闭右开**区间的数组。
代码
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int length1 = nums1.length;
int length2 = nums2.length;
int[] intersection = new int[Math.min(length1,length2)];
int index1 = 0, index2 = 0,index = 0;
while(index1 < length1 && index2 < length2 ){
if(nums1[index1] > nums2[index2]){
index2++;
}else if(nums1[index1] < nums2[index2]){
index1++;
}else{
intersection[index++] = nums1[index1];
index1++;
index2++;
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
}