```
给定两个数组,编写一个函数来计算它们的交集。
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2,2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[4,9]
说明:
输出结果中每个元素出现的次数,应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。
进阶:
如果给定的数组已经排好序呢?你将如何优化你的算法?
如果 nums1 的大小比 nums2 小很多,哪种方法更优?
如果 nums2 的元素存储在磁盘上,内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?
```
>此题可以看成是一道传统的映射题(map映射),为什么可以这样看呢,因为我们需找出两个数组的交集元素,同时应与两个数组中出现的次数一致。这样就导致了我们需要知道每个值出现的次数,所以映射关系就成了<元素,出现次数>。剩下的就是顺利成章的解题。
代码如下:
```
public class IntersectionOfTwoArrays {
public static int[] intersect(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
intersect(nums2, nums1);
}
Map<Integer, Integer> map = new HashMap();
for(int num : nums1) {
// getOrDefault(object, defaultvalue)方法就是先get(),如果返回为空,则返回默认值
// 这里的意思是,遍历数组,统计每个数字出现的次数,最小出现1次
int count = map.getOrDefault(num, 0) + 1;
map.put(num, count);
}
// 新数组下标,长度
int index = 0;
// new 一个新数组
int newNum[] = new int[nums1.length];
// 遍历另外一个数组
for (int num : nums2) {
int count = map.getOrDefault(num, 0);
// 大于0 则表示该数字在另一个数组出现过
if (count > 0) {
// 将其加到新数组
newNum[index++] = num;
// 次数减去1
count--;
// 大于0 表示该数字存在多次,将减1后的次数覆盖到原来的次数上
if (count > 0) {
map.put(num, count);
} else {
// 小于或者等于0则删除
map.remove(num);
}
}
}
// Arrays.copyOfRange(T[ ] original,int from,int to)
// 将一个原始的数组original,从下标from开始复制,复制到上标to,生成一个新的数组。
return Arrays.copyOfRange(newNum, 0, index);
}
public static void main(String[] args) {
int[] num1 = new int[]{1,2,2,1};
int[] num2 = new int[]{2,2};
int[] num3 = intersect(num1, num2);
}
}
```
进阶方法:
>如果两个数组是有序的,则可以便捷地计算两个数组的交集。
>
>首先对两个数组进行排序,然后使用两个指针遍历两个数组。
>
>初始时,两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字,如果两个数字不相等,则将指向较小数字的指针右移一位,如果两个数字相等,将该数字添加到答案,并将两个指针都右移一位。当至少有一个指针超出数组范围时,遍历结束。
代码如下:
```
public static int[] intersect1(int[] nums1, int[] nums2) {
// 排序
Arrays.sort(nums1);
Arrays.sort(nums2);
int index1 = 0;
int index2 = 0;
int index3 = 0;
int length1 = nums1.length;
int length2 = nums2.length;
// 构建新数组
int newNum[] = new int[Math.min(length1, length2)];
while (index1 < length1 && index2 < length2) {
if (nums1[index1] < nums2[index2]) {
index1++;
} else if (nums1[index1] > nums2[index2]) {
index2++;
} else {
newNum[index3] = nums1[index1];
index1++;
index2++;
index3++;
}
}
return Arrays.copyOfRange(newNum, 0, index3);
}
```

LeetCode 进阶之路 - 两个数组的交集