题目地址
题目名称：两个数的交集
难度：⭐
题目描述：
给定两个数组，编写一个函数来计算它们的交集。
示例1：
1
2
| 输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
|
示例2：
1
2
| 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
|
说明：
- 输出结果中的每个元素一定是唯一的。
- 我们可以不考虑输出结果的顺序。
🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️解题过程🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️
解题过程：
思路：
这道题思路还比较好像，比较明确但是可能不是很简便的方法，使用多重for循环，先遍历nums1中每一个元素在nums2中查找是否存在，若存在再判断是否已经保存在输出结果中了这样可以保证输出结果每个元素的唯一性。
c++代码：(执行用时56ms，击败5.86%，内存消耗10.2M，击败78.25%)
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
| using namespace std;
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> result;
for(int i = 0; i < nums1.size(); ++i) {
for(int j = 0; j < nums2.size(); ++j) {
if(nums1[i] == nums2[j]) {
if(result.size() == 0) {
result.push_back(nums1[i]);
} else {
for(int k = 0; k < result.size(); k++) {
if(nums1[i] == result[k]) {
break;
} else if(k == result.size() - 1) {
result.push_back(nums1[i]);
}
}
}
}
}
}
return result;
}
};
|
方法一：两个集合
计算两个数组的交集，直观的方法是遍历数组 nums1，对于其中的每个元素，遍历数组 nums2 判断该元素是否在数组 nums2 中，如果存在，则将该元素添加到返回值。假设数组 nums1 和 nums2 的长度分别是 $m$ 和 $n$，则遍历数组 nums1 需要 $O(m)$ 的时间，判断 nums1 中的每个元素是否在数组 nums2 中需要 $O(n)$ 的时间，因此总时间复杂度是 $O(mn)$。
如果使用哈希集合存储元素，则可以在 $O(1)$ 的时间内判断一个元素是否在集合中，从而降低时间复杂度。
首先使用两个集合分别存储两个数组中的元素，然后遍历较小的集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值。该方法的时间复杂度可以降低到 $O(m+n)$。
代码
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
| class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> set1, set2;
for (auto& num : nums1) {
set1.insert(num);
}
for (auto& num : nums2) {
set2.insert(num);
}
return getIntersection(set1, set2);
}
vector<int> getIntersection(unordered_set<int>& set1, unordered_set<int>& set2) {
if (set1.size() > set2.size()) {
return getIntersection(set2, set1);
}
vector<int> intersection;
for (auto& num : set1) {
if (set2.count(num)) {
intersection.push_back(num);
}
}
return intersection;
}
};
|
复杂度分析
- 时间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 分别是两个数组的长度。使用两个集合分别存储两个数组中的元素需要 $O(m+n)$ 的时间，遍历较小的集合并判断元素是否在另一个集合中需要 $O(min(m,n))$ 的时间，因此总时间复杂度是 $O(m+n)$。
- 空间复杂度：$O(m+n)$，其中 $m$ 和 $n$ 分别是两个数组的长度。空间复杂度主要取决于两个集合。
方法二：排序+双指针
如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。
首先对两个数组进行排序，然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量 $pre$ 表示上一次加入答案数组的元素。
初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于 $pre$ ，将该数字添加到答案并更新 $pre$ 变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。
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
| class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
int length1 = nums1.size(), length2 = nums2.size();
int index1 = 0, index2 = 0;
vector<int> intersection;
while (index1 < length1 && index2 < length2) {
int num1 = nums1[index1], num2 = nums2[index2];
if (num1 == num2) {
if (!intersection.size() || num1 != intersection.back()) {
intersection.push_back(num1);
}
index1++;
index2++;
} else if (num1 < num2) {
index1++;
} else {
index2++;
}
}
return intersection;
}
};
|
复杂度分析
时间复杂度：$O(mlogm+nlogn)$，其中 $m$ 和 $n$ 分别是两个数组的长度。对两个数组排序的时间复杂度分别是$O(mlogm)$ 和 $O(nlogn)$，双指针寻找交集元素的时间复杂度是 $O(m+n)$，因此总时间复杂度是 $O(mlogm+nlogn)$。
空间复杂度：$O(logm+logn)$，其中 $m$ 和 $n$ 分别是两个数组的长度。空间复杂度主要取决于排序使用的额外空间。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：
看到这道题目，我首先想到的就是那种直观的解法，看完官方题解后发现还是STL模板库没有学好，unordered_set这个容器根本都没见过🤣，本来下午刚看完基础的STL模板库，以为够用了看来还是得学啊，另外对这些容器的底层实现不是很了解还有复杂度分析了解甚少不太会计算复杂度，基本分不清哪些容器的效率差异，或者说自己对这方面还不敏感觉得好像都差不多没那么重要😥，接下来抽时间好好看看STL标准库和STL源码剖析吧，🤯
