两个数组的交集
# 📃 题目描述
题目链接:349. 两个数组的交集 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定两个数组,编写一个函数来计算它们的交集。
示例 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 来帮我们去重。
那这个题目其实我们需要两个 Set,整体思路如下:
- 先处理数组 nums1 将其存入一个 Set
- 遍历数组 nums2,若某个数字在 Set 中存在,则将其存入交集 Set 中
- 最后返回这个 Set 即可
另外,上一题我们说过,对于哈希表中的 key,如果哈希值比较连续且固定,我们可以用数组的下标来等同,那显然,对于这个题目,不适合用数组来代替哈希表。
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> resSet = new HashSet<>();
// 存储 nums1
Set<Integer> set = new HashSet<>();
for (int i : nums1) {
set.add(i);
}
for (int i : nums2) {
if (set.contains(i)) {
resSet.add(i);
}
}
// set 转 数组
int[] res = new int[resSet.size()];
int index = 0;
for (Integer i : resSet) {
res[index ++] = i;
}
return res;
// 或者直接 return resSet.stream().mapToInt(Integer::intValue).toArray();
}
}
# 💥 复杂度分析
- 空间复杂度:用到了两个 Set 和一个数组,空间复杂度为 O(N);
- 时间复杂度:遍历了一遍 nums1,遍历了一遍 nums2,最后 set 转数组的时候又遍历了一遍 Set,所以总的时间复杂度是 O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10