给定两个数组，编写一个函数来计算它们的交集。
示例 1:
1
2
| 输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
|
示例 2:
1
2
| 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
|
说明：
- 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
- 我们可以不考虑输出结果的顺序。
进阶:
- 如果给定的数组已经排好序呢？你将如何优化你的算法？
- 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
- 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
方法一：哈希表
我们使用哈希表存储每个数字出现的次数。首先遍历第一个数组，统计所有数字及出现的次数。再遍历第二个数组，如果哈希表中存在这个数字，将其出现的次数减一，并将其加入到结果中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> map = new HashMap<>();
List<Integer> ansList = new ArrayList<>();
for(int num : nums1){
if(map.containsKey(num)){
map.put(num, map.get(num) + 1);
}else{
map.put(num, 1);
}
}
for(int num : nums2){
if(map.containsKey(num) && map.get(num) > 0){
ansList.add(num);
map.put(num, map.get(num) - 1);
}
}
int n = ansList.size();
int[] ans = new int[n];
for(int i = 0; i < n; i++){
ans[i] = ansList.get(i);
}
return ans;
}
}
|
时间复杂度O(m + n)，其中 m 和 n 为两个数组的长度。空间复杂度O(max(m, n))。
方法二：排序
如果两个数组是有序的，可以便捷的计算两个数组的交集。首先将两个数组进行排序，然后使用两个指针遍历数组。初始时，两个指针分别指向两个数组的头部，每次比较两个指针指向的两个数组中的数字，如果两个数字相等，将当前数字加入结果中，将两个指针后移；如果两个数字不相等，将较小数字的指针向后移动。当至少一个指针遍历到数组末尾时结束循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int[] intersection = new int[Math.min(nums1.length, nums2.length)];
int index = 0;
for(int i = 0, j = 0; i < nums1.length && j < nums2.length; ){
if(nums1[i] < nums2[j]){
++i;
}else if(nums1[i] > nums2[j]){
++j;
}else{
intersection[index++] = nums1[i];
++i;
++j;
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
}
|
时间复杂度O(mlogm + nlogn)，m 和 n 分别是两个数组的长度。
空间复杂度O(min(m, n))。