两个数组的交集
题目
两个数组的交集（力扣：349）
给定两个数组，编写一个函数来计算它们的交集。
说明：
输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。
分析
本题的要点是：
找到交集元素。结果要去重。
方法一：使用Set的特性（不允许重复），把数组1保存在HashSet中，然后遍历数组2的值，如果当前值已存在Set中，则该值为交集。同理，我们将交集保存在Set中去重，最后转换成int数组返回。
方法二：遍历数组1，将int值的最小值和最大值边界找到；创建一个以最大值和最小值的差为大小的布尔数组，用于保存是否交集（true）表示交集。然后遍历数组2，当数组2中的值在数组1最大、最小值范围内，并且对应的布尔值为true，则保存，保存后将对应的布尔值置位false，来避免重复。
代码实现：方法一
/**
* 349. 两个数组的交集
* @param nums1
* @param nums2
* @return
*/
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
for (int i=0;i<nums1.length;i++){
set1.add(nums1[i]);
}
Set<Integer> resSet = new HashSet<>();
for (int j=0;j<nums2.length;j++){
if (set1.contains(nums2[j])){
resSet.add(nums2[j]);
}
}
int[] res = new int[resSet.size()];
int k = 0;
for (Integer v : resSet){
res[k] = v;
k++;
}
return res;
}
代码实现：方法二
/**
* 349. 两个数组的交集
* @param nums1
* @param nums2
* @return
*/
public int[] intersection2(int[] nums1, int[] nums2) {
// 确定数组 nums1 的取值范围
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int num : nums1) {
if (num > max) {
max = num;
}
if (num < min) {
min = num;
}
}
boolean[] arr = new boolean[max - min + 1];
for (int num : nums1) {
arr[num - min] = true;
}
// 判断数组 nums2 中的数是否在数组 nums1 中存在，
// 如果存在保存在数组 tmp 中
int[] tmp = new int[max - min + 1];
int idx = 0;
for (int num : nums2) {
if (num >= min && num <= max && arr[num - min]) {
tmp[idx++] = num;
arr[num- min] = false;//保证每个值只存储一次
}
}
// 修剪数组，返回结果
int[] ret = new int[idx];
for (int i = 0; i < idx; i++) {
ret[i] = tmp[i];
}
return ret;
}
测试结果：方法二的效率明显高于方法一。
