目标
给你两个整数数组 nums1 和 nums2，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]说明：
- 1 <= nums1.length, nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 1000
进阶：
- 如果给定的数组已经排好序呢？你将如何优化你的算法？
- 如果 nums1 的大小比 nums2 小，哪种方法更优？
- 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
思路
求两个数组 nums1 和 nums2 的交集（不考虑元素顺序），比如 a b c b 与 e b d 的交集为 b。
使用哈希表对数组 nums1 的元素值计数，遍历 nums2 获取对应元素在 nums1 中的数量，如果大于0，将元素加入列表，并将数量减一。
如果已经排好序可以直接使用双指针，每次比较移动元素值小的指针。
交集的最大元素不会超过两个数组长度的最小值，因此初始化时可以取长度较小的数组进行计数。
如果 nums2 存储在磁盘上，根据上面的讨论，我们对 nums1 计数，每次从磁盘读取一部分数据进行判断即可。
代码
/**
* @date 2025-01-30 21:37
*/
public class Intersect350 {
public int[] intersect_v2(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
intersect_v2(nums2, nums1);
}
Arrays.sort(nums1);
Arrays.sort(nums2);
int[] res = new int[nums1.length];
int j = 0;
int index = 0;
for (int i = 0; i < nums2.length && j < nums1.length; i++) {
while (j < nums1.length && nums2[i] > nums1[j]) {
j++;
}
if (j == nums1.length) {
break;
}
if (nums2[i] == nums1[j]) {
res[index++] = nums1[j];
j++;
}
}
return Arrays.copyOfRange(res, 0, index);
}
public int[] intersect_v1(int[] nums1, int[] nums2) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int i : nums1) {
cnt.merge(i, 1, Integer::sum);
}
List<Integer> list = new ArrayList<>();
for (int i : nums2) {
int value = cnt.getOrDefault(i, 0) - 1;
if (value >= 0) {
list.add(i);
cnt.put(i, value);
}
}
return list.stream().mapToInt(i -> i).toArray();
}
}
性能
