代码随想录-哈希表 | 349 两个数组的交集

本文主要是介绍代码随想录-哈希表 | 349 两个数组的交集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LeetCode 349-两个数组的交集

题目链接

题目描述

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

解题思路

判断：

• 我的思路：用数组做哈希表
  • 找到两个数组的交集：分别定义两个0-1000的布尔数组 record1 和 record2，初始化都为false，记录各个数字是否出现。再遍历这两个数组，若相同位置都为 true，则该位置所对应的数字属于 nums1 和 nums2 的交集。将其存储到 ArrayList 中。（动态数组）
  • 返回这个交集数组：由于要求返回的是 int[] 类型的数组，因此额外定义一个数组 result，遍历 ArrayList，将其中元素记录在 result 中。
• 其他思路：用set做哈希表
  • 见代码实现。

遇到哈希问题，直接使用 set 不仅占用空间比数组大，而且速度要比数组慢，set 把数值映射到 key 上都需要做 Hash 计算的。在数据量大的情况下，这个耗时的差距是很明显的。

代码

我的思路(类似哈希数组)：1ms, 41.9MB

class Solution {public int[] intersection(int[] nums1, int[] nums2) {boolean[] record1 = new boolean[1001];boolean[] record2 = new boolean[1001];for (int i = 0; i < nums1.length; i++) {record1[nums1[i]] = true;}for (int i = 0; i < nums2.length; i++) {record2[nums2[i]] = true;}ArrayList<Integer> similar = new ArrayList<Integer>();for (int i = 0; i < record1.length; i++) {if (record1[i] && record2[i]) {similar.add(i);}}int[] result= new int[similar.size()];for (int i = 0; i < similar.size(); i++){result[i] = similar.get(i);}return result;}
}

使用 Hash 数组：2ms, 42.3MB

class Solution {public int[] intersection(int[] nums1, int[] nums2) {int[] hash1 = new int[1002];int[] hash2 = new int[1002];for(int i : nums1)hash1[i]++;for(int i : nums2)hash2[i]++;List<Integer> resList = new ArrayList<>();for(int i = 0; i < 1002; i++)if(hash1[i] > 0 && hash2[i] > 0)resList.add(i);int index = 0;int res[] = new int[resList.size()];for(int i : resList)res[index++] = i;return res;}
}

使用 HashSet：4ms, 42.5MB

import java.util.HashSet;
import java.util.Set;class Solution {public int[] intersection(int[] nums1, int[] nums2) {if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {return new int[0];}Set<Integer> set1 = new HashSet<>();Set<Integer> resSet = new HashSet<>();//遍历数组1for (int i : nums1) {set1.add(i);}//遍历数组2的过程中判断哈希表中是否存在该元素for (int i : nums2) {if (set1.contains(i)) {resSet.add(i);}}//方法1：将结果集合转为数组return resSet.stream().mapToInt(x -> x).toArray();//方法2：另外申请一个数组存放setRes中的元素,最后返回数组int[] arr = new int[resSet.size()];int j = 0;for(int i : resSet){arr[j++] = i;}return arr;}
}

复杂度

• 时间复杂度
  时间复杂度为O(n + m)，m 是最后要把 set 转成vector
• 空间复杂度
  O(n)

难点

• 哈希表的使用
  • 如果题目没有限制数组的大小，无法使用数组来做哈希表。
  • 如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。此时应该使用另一种结构体，set。

总结

学习到新知识：对 数组 和 set 哈希表的使用场景有了更深的了解。

这篇关于代码随想录-哈希表 | 349 两个数组的交集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---