【C++刷题】力扣-#349-两个数组的交集

题目描述

给定两个数组 nums1 和 nums2，返回它们的交集。输出结果中的每个数字，只能出现一次，并且按非递减顺序排列。

示例

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

题解

这个问题可以通过使用哈希表来解决。我们可以将一个数组的元素存储到哈希表中，然后遍历另一个数组，检查每个元素是否在哈希表中。

1. 初始化哈希表：创建一个哈希表 numSet 来存储 nums1 中的元素。
2. 构建哈希表：遍历 nums1，将每个元素添加到 numSet 中。
3. 查找交集：创建一个空列表 intersection 来存储交集结果。
   ○ 遍历 nums2，对于 nums2 中的每个元素，检查它是否存在于 numSet 中。
   ○ 如果存在，并且该元素还没有被添加到 intersection 中，则将其添加到 intersection 中。
4. 排序结果：由于题目要求结果按非递减顺序排列，我们可以使用标准库中的排序函数对 intersection 进行排序。
5. 返回结果：返回排序后的 intersection 列表。

代码实现

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> numSet(nums1.begin(), nums1.end());vector<int> intersection;for (int num : nums2) {if (numSet.find(num) != numSet.end()) {intersection.push_back(num);numSet.erase(num); // 确保每个元素只添加一次}}return intersection;
}

复杂度分析

● 时间复杂度：O(n + m + k log k)，其中 n 是 nums1 的长度，m 是 nums2 的长度，k 是交集的大小。我们需要遍历两个数组，并且对结果进行排序。
● 空间复杂度：O(n)，我们需要存储 nums1 中的所有元素到哈希表中。
这个算法的优势在于它的时间效率较高，只需要一次遍历即可找到两个数组的交集，且直接利用了哈希表的快速查找特性。