查找表：考虑的基本数据结构
第一类： 查找有无--set
元素‘a‘是否存在，通常用set：集合
set只存储键，而不需要对应其相应的值。
set中的键不允许重复
第二类： 查找对应关系(键值对应)--map
元素‘a‘出现了几次：dict-->字典
dict中的键不允许重复
第三类： 改变映射关系--map
通过将原有序列的关系映射统一表示为其他
题目描述：
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
说明：
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
解题思路：
用两个HashSet分别统统计两个数组，然后找出两个set中公共元素
代码：
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> set1 = new HashSet<>();
for (Integer num : nums1) {
set1.add(num);
}
HashSet<Integer> set2 = new HashSet<>();
for (Integer num : nums2) {
set2.add(num);
}
return set1.size() < set2.size() ? help(set1, set2) : help(set2, set1);
}
private int[] help(HashSet<Integer> set1, HashSet<Integer> set2) {
int[] output = new int[set1.size()];
int index = 0;
for (Integer s : set1){
if (set2.contains(s))
output[index++] = s;
}
return Arrays.copyOf(output, index);
}
复杂度分析：
题目描述：
给定两个数组，编写一个函数来计算它们的交集。
示例 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?的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
解题思路：
跟上一道题目不同的是，这个可以有重复元素，所以可以考虑采用hashmap
方法一：采用上述题目的套路，效率低
方法二：使用hash表存储，效率高
方法一：
public int[] intersect(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> map1 = new HashMap<>();
HashMap<Integer, Integer> map2 = new HashMap<>();
for (int i = 0; i < nums1.length; i++) {
map1.put(nums1[i], map1.getOrDefault(nums1[i], 0) + 1);
}
for (int i = 0; i < nums2.length; i++) {
map2.put(nums2[i], map2.getOrDefault(nums2[i], 0) + 1);
}
int n = nums1.length < nums2.length ? nums1.length : nums2.length;
int[] output = new int[n];
int index = 0;
for (Map.Entry<Integer, Integer> map : map1.entrySet()) {
if (map2.containsKey(map.getKey())) {
int temp = map2.get(map.getKey()) < map.getValue() ? map2.get(map.getKey()) : map.getValue();
for (int i = 0; i < temp; i++) {
output[index++] = map.getKey();
}
}
}
return Arrays.copyOf(output, index);
}
复杂度分析：
方法二：采用hash表
思路：
由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。
首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。
为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。
public int[] intersect2(int[] nums1, int[] nums2) {
// 保证 nums1的长度始终最小
if (nums1.length > nums2.length)
return intersect2(nums2, nums1);
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums2.length; i++) {
map.put(nums2[i], map.getOrDefault(nums2[i], 0) + 1);
}
int n = nums1.length;
int[] output = new int[n];
int index = 0;
for (Integer num : nums1) {
int count = map.getOrDefault(num, 0);
if (count > 0) {
output[index++] = num;
count--;
if (count > 0) {
map.put(num, count);
} else {
map.remove(num);
}
}
}
return Arrays.copyOf(output, index);
}
复杂度分析：
两者性能对比：
未完待续
原文：https://www.cnblogs.com/guohaoblog/p/13562498.html