0349. Intersection of Two Arrays ================================ 题目信息 -------- :题号: 0349 :难度: Easy :主题: 两个数组、集合交集、结果去重、顺序不限 :原题: `LeetCode 0349 `_ :重点: 元素必须同时出现在两个数组中、每个共同值只返回一次、输入中的重复次数不影响结果 题目重述 -------- 给定两个整数数组 ``nums1`` 和 ``nums2``,返回它们的集合交集:某个整数只有在两个数组中都至少出现一次时才属于结果。 结果中的每个整数必须唯一,即使它在输入数组中重复多次也只能返回一次;结果顺序不限。两个数组长度均位于 ``[1, 1000]``,元素位于 ``[0, 1000]``。 自建示例 -------- 输入包含多个重复值: .. code-block:: text 输入:nums1 = [1, 2, 2, 4],nums2 = [2, 2, 3, 4, 4] 输出:[2, 4] 解释:2 和 4 都在两个数组中出现,但集合交集只保留每个共同值一次;输出顺序可以是 [4,2]。 没有共同元素: .. code-block:: text 输入:nums1 = [0, 1],nums2 = [2, 3] 输出:[] 解释:不存在同时出现在两个数组中的整数。 把第一个数组变成待匹配集合 ---------------------------- 将 ``nums1`` 的值放入集合,扫描 ``nums2`` 时若当前值仍在集合中,就把它加入答案并从集合删除。删除的作用是同时完成去重:后续即使再次遇到同一值,也不会再次输出。集合中最终只保留“尚未在第二个数组中匹配”的第一个数组值。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::vector intersection( std::vector& nums1, std::vector& nums2) { std::unordered_set candidates( nums1.begin(), nums1.end()); std::vector result; for (int value : nums2) { auto it = candidates.find(value); if (it == candidates.end()) continue; result.push_back(value); candidates.erase(it); } return result; } }; 代码分析 -------- 集合只表达是否出现过,不记录频次,符合普通集合交集的定义;从候选集合删除后保证每个共同值只输出一次。哈希集合操作平均为常数时间,时间复杂度为 ``O(nums1.size() + nums2.size())``,额外空间为 ``O(nums1.size())``。