文章目录
一、题目
给定两个数组,编写一个函数来计算它们的交集。
二、哈希思路
暴力破解的思路就是遍历 nums1 的过程中,遍历 nums2 ,时间复杂度 O ( n 2 ) O(n^2) O(n2)
题目已经说明,输出结果中每个元素唯一,可以把 nums1 的元素映射到哈希数组上,然后遍历 nums2时,判断是否出现过就可以
对于数组的使用,需要限制数值的大小,而且如果哈希值比较少,特别分散,跨度大,使用数组就容易造成空间的浪费
所以,本题采用 set 集合充当哈希表,也符合题目要求的去重效果
三、代码
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<>();
//遍历数组1
for (int i : nums1) {
set1.add(i);
}
//遍历数组2的过程中判断哈希表中是否存在该元素
for (int i : nums2) {
if (set1.contains(i)) {
resSet.add(i);
}
}
int[] resArr = new int[resSet.size()];
int index = 0;
//将结果几何转为数组
for (int i : resSet) {
resArr[index++] = i;
}
return resArr;
}
}
四、总结
对于数组的使用,需要限制数值的大小,而且如果哈希值比较少,特别分散,跨度大,使用数组就容易造成空间的浪费
所以,对于没有说明数值大小,或者有去重需求的题目采用 set 集合充当哈希表
//set集合添加元素
set.add(i);
//获取set集合大小
set.size();
//判断set集合是否存在某元素
if(set.contains(i)){
System.out.println("存在");
}