力扣349 == 两个数组交集的两种解法
目录
解法一:利用 Set 特性高效去重
解法二:双重遍历与 Set 去重
方法对比与总结
关键点总结
题目描述
给定两个整数数组 nums1
和 nums2
,要求返回它们的交集。输出结果中的每个元素必须是唯一的,且顺序不限。
示例
-
输入:
nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
-
输入:
nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
或[4,9]
解法一:利用 Set 特性高效去重
思路
-
将
nums1
转换为Set
结构,自动去重。 -
遍历
nums2
,检查元素是否存在于Set
中:-
若存在,则将该元素加入结果数组,并从
Set
中删除,避免后续重复匹配。
-
-
最终返回结果数组。
代码实现
var intersection = function(nums1, nums2) {const st = new Set(nums1);const ans = [];for (const x of nums2) {if (st.delete(x)) { // 如果元素存在,删除并收集ans.push(x);}}return ans;
};
复杂度分析
-
时间复杂度:O(m + n),其中
m
和n
是数组长度。
转换nums1
为Set
需要 O(m),遍历nums2
需要 O(n)。 -
空间复杂度:O(m),用于存储
Set
。
优势
-
高效处理重复元素:通过
st.delete(x)
确保每个元素只匹配一次。 -
线性时间复杂度,适合处理大数据量。
解法二:双重遍历与 Set 去重
思路
-
遍历
nums1
,对每个元素检查是否存在于nums2
中。 -
若存在,则将其加入
Set
自动去重。 -
最终将
Set
转为数组返回。
代码实现
var intersection = function(nums1, nums2) {let set = new Set();for (let i = 0; i < nums1.length; i++) {if (nums2.includes(nums1[i])) {set.add(nums1[i]);}}return Array.from(set);
};
复杂度分析
-
时间复杂度:O(m × n),最坏情况下需遍历
nums2
的每个元素。 -
空间复杂度:O(k),
k
为交集元素的数量。
缺点
-
nums2.includes()
的时间复杂度为 O(n),当数组较大时性能较差。
方法对比与总结
特性 | 解法一(Set + 删除) | 解法二(双重遍历 + Set) |
---|---|---|
时间复杂度 | O(m + n) | O(m × n) |
空间复杂度 | O(m) | O(k) |
处理重复元素 | 立即删除,避免重复匹配 | 依赖 Set 去重 |
适用场景 | 大数据量 | 小数据量或简单场景 |
推荐解法
优先选择解法一,因为它利用 Set
的高效查找和删除操作,时间复杂度更低,尤其适合处理大规模数据。解法二虽然代码更直观,但性能较差,仅在数据量较小时适用。
关键点总结
-
去重机制:使用
Set
结构天然去重。 -
性能优化:通过删除已匹配元素减少重复检查。
-
方法选择:根据数据规模选择时间复杂度更优的解法。