分析
- 使用哈希集合存储唯一元素：
- 为了处理数组中重复的元素，我们使用两个集合
hash1 和 hash2 分别存储 nums1 和 nums2 的唯一值
- 查找差集：
- 遍历集合
hash1，找出不在 hash2 中的元素，存入 res[0]
- 遍历集合
hash2，找出不在 hash1 中的元素，存入 res[1]
- 返回结果：
时间复杂度
- 遍历数组构建集合的时间是
O(n + m)
- 遍历集合查找差集的时间是
O(n + m)
总时间复杂度：O(n + m)，其中 n 和 m 分别是 nums1 和 nums2 的长度
空间复杂度
空间复杂度：O(u + v)，其中 u 和 v 是 nums1 和 nums2 中的不同元素个数
C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class Solution {
public:
vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2)
{
// 使用集合存储唯一元素
std::unordered_set<int> hash1;
std::unordered_set<int> hash2;
// 将 nums1 的元素加入 hash1
for (int num : nums1)
hash1.insert(num);
// 将 nums2 的元素加入 hash2
for (int num : nums2)
hash2.insert(num);
std::vector<std::vector<int>> res(2);
// 找出 nums1 中不在 nums2 中的元素
for (int num : hash1)
if (!hash2.count(num))
res[0].push_back(num);
// 找出 nums2 中不在 nums1 中的元素
for (int num : hash2)
if (!hash1.count(num))
res[1].push_back(num);
return res;
}
};
|
