349、两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
说明：
- 输出结果中的每个元素一定是唯一的。
- 我们可以不考虑输出结果的顺序。
- 通过次数78,765提交次数112,680
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays
题解
1、用两个set
class Solution {
public int[] set_intersection(HashSet<Integer> set1, HashSet<Integer> set2) {
int [] output = new int[set1.size()];
int idx = 0;
for (Integer s : set1)
if (set2.contains(s)) output[idx++] = s;
return Arrays.copyOf(output, idx);
}
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> set1 = new HashSet<Integer>();
for (Integer n : nums1) set1.add(n);
HashSet<Integer> set2 = new HashSet<Integer>();
for (Integer n : nums2) set2.add(n);
if (set1.size() < set2.size()) return set_intersection(set1, set2);
else return set_intersection(set2, set1);
}
}
// 链接：https://leetcode-cn.com/problems/intersection-of-two-arrays/solution/liang-ge-shu-zu-de-jiao-ji-by-leetcode/
2、语言API
class Solution {
public int[] set_intersection(HashSet<Integer> set1, HashSet<Integer> set2) {
int [] output = new int[set1.size()];
int idx = 0;
for (Integer s : set1)
if (set2.contains(s)) output[idx++] = s;
return Arrays.copyOf(output, idx);
}
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> set1 = new HashSet<Integer>();
for (Integer n : nums1) set1.add(n);
HashSet<Integer> set2 = new HashSet<Integer>();
for (Integer n : nums2) set2.add(n);
if (set1.size() < set2.size()) return set_intersection(set1, set2);
else return set_intersection(set2, set1);
}
}
// 链接：https://leetcode-cn.com/problems/intersection-of-two-arrays/solution/liang-ge-shu-zu-de-jiao-ji-by-leetcode/
350、两个数组的交集 II
给定两个数组，编写一个函数来计算它们的交集。
示例 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 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
> 链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii
# 题解
## 1、哈希表
```java
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
// 用哈希表存储元素数量较少的数组
if (nums1.length > nums2.length) {
return intersect(nums2, nums1);
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums1) {
int count = map.getOrDefault(num, 0) + 1;
map.put(num, count);
}
// 检索有公有的元素
int[] intersection = new int[nums1.length];
int index = 0;
for (int num : nums2) {
int count = map.getOrDefault(num, 0);
if (count > 0) {
intersection[index++] = num;
count--;
if (count > 0) {
map.put(num, count);
} else {
map.remove(num);
}
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
}
2、排序 归并
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int length1 = nums1.length, 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]) {
index1++;
} else if (nums1[index1] > nums2[index2]) {
index2++;
} else {
intersection[index] = nums1[index1];
index1++;
index2++;
index++;
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
}
// 链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/solution/liang-ge-shu-zu-de-jiao-ji-ii-by-leetcode-solution/
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
