:-: 1.9 两个数组的交集
*****
**题干**
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
```
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
```
示例 2:
```
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]
```
说明:
```
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
```
**题目分析：**
一看求交集且结果元素不重复，就想到了Set集合无重复值的特性，也可使用其他集合，手动控制不重复。
**新手有可能遇到的解题思路陷阱：**
注意结果集中元素不重复也不允许有其他数组默认值。
**解题思路分析以及代码实现：**
第一种思路：双重嵌套循环+Set集合。
第一种思路代码：
```
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
if (nums1[i] == nums2[j]) {
//元素相等就加入，Set处理重复值
set.add(nums1[i]);
break;
}
}
}
int[] nums = new int[set.size()];
int i = 0;
for (int n : set) {
nums[i] = n;
i++;
}
return nums;
}
```
第一种思路：双重嵌套循环+其他集合手动处理重复值。
```
public int[] intersection(int[] nums1, int[] nums2) {
ArrayList<Integer> tmp = new ArrayList<>();
for (int i = 0; i < nums1.length; i++) {
//利用indexOf()或者contains()方法判断是否重复
for (int j = 0; j < nums2.length; j++) {
if (nums1[i] == nums2[j] && tmp.indexOf(nums1[i]) < 0) {
tmp.add(nums1[i]);
}
}
}
int[] result = new int[tmp.size()];
for (int i = 0; i < tmp.size(); i++) {
result[i] = tmp.get(i);
}
return result;
}
```
```
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> result_set = new HashSet();
for (int num1 : nums1) {
for (int num2 : nums2) {
if (num1 == num2)
result_set.add(num1);
}
}
//将Set集合转化为数组，简化遍历Set集合的时间
Integer[] result_ = result_set.toArray(new Integer[result_set.size()]);
int[] result = new int[result_.length];
for (int i = 0; i < result_.length; i++) {
result[i] = result_[i];
}
return result;
}
```
**复杂度分析**
时间复杂度：O(n^2)。
空间复杂度：O(n)。
第二种思路：排序法。
第二种思路代码：
```
public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
ArrayList result = new ArrayList();
int mark = 0;
for (int i = 0, j = 0; i < nums1.length && j < nums2.length;) {
if (nums1[i] == nums2[j]) {
//因为已经经过排序，只需验证前一个与当前是否相同即可
if (result.size() == 0 || nums1[i] != mark) {
result.add(nums1[i]);
mark = nums1[i];
}
i++;
j++;
} else if (nums1[i] < nums2[j]) {
i++;
} else {
j++;
}
}
int[] res = new int[result.size()];
for (int i = 0; i < result.size(); i++) {
res[i] = (int) result.get(i);
}
return res;
}
```
**复杂度分析**
时间复杂度：O(n)。
空间复杂度：O(n)。
第三种思路：利用Java集合自带方法。
为什么将int类型数组转化为Integer类型数组？[Arrays.asList()方法使用](http://blog.sina.com.cn/s/blog_6a6badc90101550l.html)
Java集合的求交集，差集方法：[Java集合的求交集，差集方法](https://blog.csdn.net/difffate/article/details/72540220)
第三种思路代码：
```
public int[] intersection(int[] nums1, int[] nums2) {
int sizenums1 = nums1.length;
int sizenums2 = nums2.length;
Integer[] nums12 = new Integer[sizenums1];
Integer[] nums22 = new Integer[sizenums2];
for (int i = 0; i < sizenums1; i++) {
nums12[i] = new Integer(nums1[i]);
}
for (int i = 0; i < sizenums2; i++) {
nums22[i] = new Integer(nums2[i]);
}
Set<Integer> copy = new HashSet<Integer>();
copy.addAll(Arrays.asList(nums12));
copy.retainAll(Arrays.asList(nums22));
int[] ans = new int[copy.size()];
int i = 0;
for (int num : copy) {
ans[i++] = num;
}
return ans;
}
```
**复杂度分析**
时间复杂度：O(n)。
空间复杂度：O(n)。
第四种思路：空间换时间，双集合。
第四种思路代码：
```
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> result = new HashSet<>();
Set<Integer> set = new HashSet<>();
// 先将num1全放sets里
for (int i = 0; i < nums1.length; i++) {
set.add(nums1[i]);// 放入时候去掉重复的
}
for (int j = 0; j < nums2.length; j++) {
if (set.contains(nums2[j])) {
result.add(nums2[j]);// 放入交集
}
}
int[] arr = new int[result.size()];
Object[] a = result.toArray();
for (int i = 0; i < a.length; i++) {
arr[i] = (int) a[i];
}
return arr;
}
```
**复杂度分析**
时间复杂度：O(n)。
空间复杂度：O(n)。
第五种思路：排序后查找。
第五种思路代码：
```
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Arrays.sort(nums1);
for (int i = 0; i <= nums2.length - 1; i++) {
int top = 0;
int bottom = nums1.length - 1;
while (top <= bottom) {
int mid = top + (bottom - top) / 2;
if (nums1[mid] == nums2[i]) {
set.add(nums1[mid]);
break;
}
if (nums1[mid] < nums2[i]) {
top = mid + 1;
} else {
bottom = mid - 1;
}
}
}
int[] result = new int[set.size()];
int i = 0;
for (int num : set) {
result[i] = num;
i++;
}
return result;
}
```
**复杂度分析**
时间复杂度：O(n * logn)。
空间复杂度：O(n)。
第六种思路：标记法。不使用集合，只使用数组，大大减少了时间。
第六种思路代码：
```
public int[] intersection(int[] nums1, int[] nums2) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
// 求出数组nums1中最大值 与最小值
for (int i = 0; i < nums1.length; i++) {
max = max < nums1[i] ? nums1[i] : max;
min = min > nums1[i] ? nums1[i] : min;
}
// 标记
boolean[] booleanArray = new boolean[max - min + 1];
for (int i = 0; i < nums1.length; i++) {
booleanArray[nums1[i] - min] = true;
//去重并加标记
}
int index = 0;
int[] tempArray = new int[nums2.length];
for (int i = 0; i < nums2.length; i++) {
// 找出nums2中的元素，标记改为false
if (!(nums2[i] < min) && !(nums2[i] > max) && booleanArray[nums2[i] - min]) {
booleanArray[nums2[i] - min] = false;
//去重
// 找出相同的数据
tempArray[index++] = nums2[i];
}
}
// 复制有数值位，舍弃默认数值位
return Arrays.copyOf(tempArray, index);
}
```
**复杂度分析**
时间复杂度：O(n)。
空间复杂度：O(n)。
**若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**
- 前言
- 第一部分 初级入门算法
- 第一章 数组
- 1.1 删除排序数组中的重复项
- 1.2 删除排序数组中的重复项 II
- 1.3 买卖股票的最佳时机
- 1.4 买卖股票的最佳时机 II
- 1.5 移动零
- 1.6 区间子数组个数
- 1.7 搜索插入位置
- 1.8 合并两个有序数组
- 1.9 两个数组的交集
- 第二章 哈希表
- 2.1 两数之和
- 2.2 错误的集合
- 2.3 翻转卡片游戏
- 2.4 有效的字母异位词
- 第三章 链表
- 第四章 数学
- 4.1 加一
- 4.2 反转整数
- 4.3 排列硬币
- 4.4 完全平方数
- 4.5 消除游戏
- 第五章 双指针
- 第六章 字符串
- 6.1 整数转罗马数字
- 6.2 罗马数字转整数
- 6.3 反转字符串
- 6.4 压缩字符串
- 6.5 验证回文串
- 6.6 长按键入
- 6.7 字符串中的第一个唯一字符
- 第七章 二分查找
- 7.1 猜数字大小
- 第八章 分治算法
- 第九章 动态规划
- 9.1 爬楼梯
- 9.2 使用最小花费爬楼梯
- 9.3 打家劫舍
- 9.4 打家劫舍 II
- 9.5 第N个泰波那契数
- 第十章 回溯算法
- 第十一章 栈
- 11.1 棒球比赛
- 第十二章 堆
- 12.1 数组中的第K个最大元素
- 第十三章 贪心算法
- 第十四章 排序
- 14.1 冒泡排序
- 14.2 鸡尾酒排序
- 14.3 选择排序
- 14.4 插入排序
- 14.5 折半插入排序
- 14.6 希尔排序
- 14.7 快速排序
- 14.8 树形选择排序
- 14.9 堆排序
- 第十五章 位运算
- 15.1 只出现一次的数字
- 第十六章 思维题
- 16.1 TinyURL 的加密与解密
- 16.2 灯泡开关
- 16.3 字母板上的路径
- 第十七章 队列
- 17.1 扑克牌顺序