350两个数组的交集
我写了有点麻烦了,用了两个哈希表,实际上一个就够了,题解的两个方法是哈希表和排序+双指针,都挺有收获的
#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
//自己写的, 两个哈希表,太麻烦了
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int>map1;
unordered_map<int, int>map2;
vector<int>ans;
for (int i = 0; i < nums1.size(); i++) {
auto it = map1.find(nums1[i]);
if (it != map1.end()) {
map1[nums1[i]]++;
}
else {
map1[nums1[i]] = 1;
}
}
for (int i = 0; i < nums2.size(); i++) {
auto it = map2.find(nums2[i]);
if (it != map2.end()) {
map2[nums2[i]]++;
}
else {
map2[nums2[i]] = 1;
}
}
for (auto it2 = map2.begin(); it2 != map2.end();it2++) {
auto it1 = map1.find(it2->first);
if (it1 != map1.end()) {
int min;
if (it1->second < it2->second) {
min = it1->second;
}
else min = it2->second;
for (int j = 0; j < min; j++) {
ans.push_back(it2->first);
}
}
}
sort(ans.begin(), ans.end());
return ans;
}
};
//题解方法一,哈希表
class Solution1 {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) {//处理短的,减少运行时间
return intersect(nums2, nums1);
}
unordered_map <int, int> m;
for (int num : nums1) {
++m[num];//可以这样写,我以前都麻烦了
}
vector<int> intersection;//返回值
for (int num : nums2) {
if (m.count(num)) {
intersection.push_back(num);
--m[num];//如果nums2中的数在哈希表中存在,就将哈希表中的数量减一,如果为0就清掉
if (m[num] == 0) {
m.erase(num);
}
}
}
return intersection;
}
};
//题解方法二,双指针
class Solution2 {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());//排序成有序数组
int length1 = nums1.size(), length2 = nums2.size();
vector<int> intersection;
int index1 = 0, index2 = 0;
while (index1 < length1 && index2 < length2) {
if (nums1[index1] < nums2[index2]) {
index1++;
}
else if (nums1[index1] > nums2[index2]) {
index2++;
}
else {
intersection.push_back(nums1[index1]);
index1++;
index2++;
}
}
return intersection;
}
};
int main() {
Solution test;
vector<int>nums1 = {4,9,5};
vector<int>nums2 = {9,4,9,8,4};
vector<int>ans = test.intersect(nums1, nums2);
for (int i = 0; i < ans.size(); i++) {
cout << ans[i];
}
}