AlgoPressAppearance
0350-两个数组的交集II
https://leetcode.cn/problems/intersection-of-two-arrays-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的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
基本思路
遍历循环第两个数组，发现相同的数字
- 加入List，则第二个数组中置为负数，这样不会重复计算
- break 退出第二层循环，防止重复 add list
参考代码
csharp
public class Solution {
public int[] Intersect(int[] nums1, int[] nums2) {
List<int> list = new List<int>();
for(int i=0; i<nums1.Length; i++){
for(int j=0; j<nums2.Length; j++){
if(nums1[i] == nums2[j]){
list.Add(nums1[i]);
//nums2置为负数，并且退出第二层循环，防止重复计算
nums2[j] = -1;
break;
}
}
}
return list.ToArray();
}
}
思路2：【官方】使用hash表缓存数字个数
- 将第一个数组数字放到hash表中
- 遍历第二个数组，如果发现 hash 表中有，则增加到 list 中去
- 扣减 hash 表数字的 count ， 如果是0，则不去计算
算法复杂度O(max(m,n))
参考代码
csharp
public class Solution {
public int[] Intersect(int[] nums1, int[] nums2) {
List<int> list = new List<int>();
Dictionary<int,int> dict = new Dictionary<int,int>();
for(int i=0; i < nums1.Length; i++){
if(!dict.ContainsKey(nums1[i])){
dict.Add(nums1[i],1);
}
else{
dict[nums1[i]]++;
}
}
for(int j=0; j<nums2.Length; j++){
if(dict.ContainsKey(nums2[j]) && dict[nums2[j]] > 0){
list.Add(nums2[j]);
dict[nums2[j]]--;
}
}
return list.ToArray();
}
}
进阶思路
- 如果是排序好的数组，就用双指针按顺序移动，
- 数字小的先移动
- 如果相等就等于找到一个结果，两个同时移动
- 一个指针到达末尾，就结束
- nums1 小就先循环 nums2
- 每次读取一部分 nums2 进行处理即可