16-算法打卡-哈希表-两个数组的交集-leetcode(349)-第十六天

1 题目地址

349. 两个数组的交集 - 力扣（LeetCode）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] <= 1000https://leetcode.cn/problems/intersection-of-two-arrays/description/

2 题目说明

给定两个数组 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

3 解题思路

方式一：使用HashSet
1、将数组nums1的数据放入到HashSet中
2、遍历nums2中的数据是否存在HashSet中，存在在放入到另外一个HashSet中

方式二：使用哈希表(数组) 【题干中限制了nums1 nums2的长度、数值都小于等于1000】
如果题干没有限制，其实是不太适合用哈希表实现的，而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
1、创建两个数组nums1Array、nums2Array长度都为1001
                (nums[i]=1000需要往nums1Array[1000]=1；数组长度设置成1000会报数组下标越界)
2、分别遍历nums1,nums2，将数据分别放入到nums1Array、nums2Array； nums1[i]的值映射成数组的index，出现的次数映射成value
3、判断两个数组nums1Array、nums2Array中的索引下标对应的value都大于0表示存在相同的数字。

4 代码编写

4.1 HashSet方式

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> nums1Set = new HashSet<>();Set<Integer> resultSet = new HashSet<>();for (int i=0; i<nums1.length; i++) {nums1Set.add(nums1[i]);}for (int i=0; i<nums2.length; i++) {if (nums1Set.contains(nums2[i])) {resultSet.add(nums2[i]);}}return resultSet.stream().mapToInt(x->x).toArray();}
}

4.2 使用hash数组

 int[] nums1Array = new int[1001];
 int[] nums2Array = new int[1001]; 
注意这块长度如果设置成1000，会报数组下标越界，当数组中存在1000的时候，就需要往nums1Array[1000]=1

class Solution {public int[] intersection(int[] nums1, int[] nums2) {int[] nums1Array = new int[1001];int[] nums2Array = new int[1001];for (int i=0; i<nums1.length; i++) {nums1Array[nums1[i]]++; // 关键码(索引)表示数据，关键值(数据)表示数量}for (int i=0; i<nums2.length; i++) {nums2Array[nums2[i]]++; // 关键码(索引)表示数据，关键值(数据)表示数量}List<Integer> resultList = new ArrayList<>();for (int i=0; i<1001; i++) {if (nums1Array[i]>0 && nums2Array[i]>0) {resultList.add(i);}}return resultList.stream().mapToInt(Integer::intValue).toArray();}
}