算法训练——day15数组交集（是否去重）

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

常规题，遍历nums1，存入哈希中，再看看nums2中的在哈希中是否存在，若存在则放入结果ret中。

class Solution {public int[] intersection(int[] nums1, int[] nums2) {if(nums1==null||nums2==null||nums1.length==0||nums2.length==0){return new int[0];}Set<Integer> set1 = new HashSet<>();Set<Integer> ret = new HashSet<>();//遍历nums1for(int num:nums1){set1.add(num);}//遍历nums2.判断哈希表中是否存在for(int num:nums2){if(set1.contains(num)){ret.add(num);}}//数组int[] retArr = new int[ret.size()];int i = 0;for(int num:ret){retArr[i++]=num;}return retArr;}
}

由于题目中限制了数组长度，所以提前开好长度可以节省时间，再用数组模拟来节省空间，如果用哈希的话就是用空间换时间。

class Solution {public int[] intersection(int[] nums1, int[] nums2) {int []hash=new int[1001];int []tmp=new int[1001];int count=0;for(int i=0;i<nums1.length;i++){hash[nums1[i]]=1;}for(int j=0;j<nums2.length;j++){if(hash[nums2[j]]==1){tmp[count++]=nums2[j];hash[nums2[j]]++;}}int []ret=new int[count];for(int k=0;k<count;k++){ret[k]=tmp[k];}return ret;}
}

350. 两个数组的交集 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 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

和前面那题的区别就是，这个题要考虑重复数字问题。首先想到的就是哈希表了，进行记录。具体解释在代码中一注释。

class Solution {public int[] intersect(int[] nums1, int[] nums2) {HashMap<Integer, Integer> map = new HashMap<>();ArrayList<Integer> list = new ArrayList<>();// 对nums1的数组遍历，存到map里面，key是数组元素值（对应map中的下标），value是出现次数for (int num : nums1) {map.put(num, map.getOrDefault(num, 0) + 1);}// 接着遍历nums2，如果上一轮中的value不为0，则进行结果存储并对该值进行减1操作for (int num : nums2) {if (map.getOrDefault(num, 0) > 0) {list.add(num);map.put(num, map.get(num) - 1);}}//转数组int[] ret = new int[list.size()];for (int i = 0; i < list.size(); i++) {ret[i] = list.get(i);}return ret;}
}

在空间上还可以进行优化，我们可以保证map的大小是最小的数组的长度，加一个判断即可。

class Solution {public int[] intersect(int[] nums1, int[] nums2) {if(nums1.length>nums2.length){return intersect(nums2,nums1);}HashMap<Integer, Integer> map = new HashMap<>();ArrayList<Integer> list = new ArrayList<>();// 对nums1的数组遍历，存到map里面，key是数组元素值（对应map中的下标），value是出现次数for (int num : nums1) {map.put(num, map.getOrDefault(num, 0) + 1);}// 接着遍历nums2，如果上一轮中的value不为0，则进行结果存储并对该值进行减1操作for (int num : nums2) {if (map.getOrDefault(num, 0) > 0) {list.add(num);map.put(num, map.get(num) - 1);}}//转数组int[] ret = new int[list.size()];for (int i = 0; i < list.size(); i++) {ret[i] = list.get(i);}return ret;}
}

用时间换空间，进行双层遍历（不实用）

class Solution {public int[] intersect(int[] nums1, int[] nums2) {List<Integer> list = new ArrayList<>();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[j] = -1;break;}}}int[] res = new int[list.size()];for (int i = 0; i < list.size(); i++) {res[i] = list.get(i);}return res;}
}

空间换时间，已知数组长度最大为1000，所以开1001长度的数组。

class Solution {public int[] intersect(int[] nums1, int[] nums2) {int[] flag = new int[1001];//作为先遍历的标记数组for (int num : nums1) {flag[num]++;}int[] tmp = new int[1001];//中间数组，暂时存储int length = 0;//记录长度for (int num : nums2) {if (flag[num] > 0) {tmp[length++] = num;flag[num]--;}}//去掉多余的0int[] ret = new int[length];System.arraycopy(tmp, 0, ret, 0, length);return ret;}
}