两个数组的交集 II
难度:
标签:
题目描述
给你两个整数数组 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
的元素存储在磁盘上,内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?
代码结果
运行时间: 19 ms, 内存: 16.2 MB
/*
* 思路:
* 1. 使用Java Stream创建一个Map来存储nums1中每个元素的出现次数。
* 2. 遍历nums2,过滤出在Map中存在且计数大于0的元素,
* 并更新Map中的计数。
* 3. 收集这些元素并返回数组。
*/
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Long> map = Arrays.stream(nums1)
.boxed()
.collect(Collectors.groupingBy(e -> e, Collectors.counting()));
List<Integer> result = Arrays.stream(nums2)
.boxed()
.filter(num -> map.getOrDefault(num, 0L) > 0)
.peek(num -> map.put(num, map.get(num) - 1))
.collect(Collectors.toList());
return result.stream().mapToInt(i -> i).toArray();
}
}
解释
方法:
该题解的思路是先对两个数组进行排序,然后使用双指针分别指向两个数组的起始位置。然后不断移动指针比较两个指针指向的元素大小,如果相等就把该元素加入答案,并同时移动两个指针;如果不相等,就移动指向较小数字的指针。这样遍历完一遍就能得到两个数组的交集。
时间复杂度:
O((n1+n2)log(n1+n2))
空间复杂度:
O(log(n1+n2))
代码细节讲解
🦆
在处理两个数组的交集时,为什么选择对数组进行排序而不是使用哈希表来存储元素频率?
▷🦆
在双指针方法中,如果两个数组中的元素重复度较高,这种方法的效率如何?
▷🦆
在进阶问题中提到如果`nums1`的大小比`nums2`小,是否考虑先对`nums1`进行排序,然后遍历`nums2`寻找交集?这样做的优势是什么?
▷🦆
对于进阶问题中的场景,如果`nums2`的元素存储在磁盘上并且内存有限,如何优化算法以减少内存使用和IO操作?
▷