两个数组的交集
数组哈希表
建立两个1000大小数组，暴力映射进去。
消耗空间过大。
#include <iostream> #include<string> #include<vector> using namespace std; class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { vector<int>record1(1000, 0); vector<int>record2(1000, 0); for (int i = 0; i < nums1.size(); i++) { record1[nums1[i]]++; } for (int i = 0; i < nums2.size(); i++) { record2[nums2[i]]++; } vector<int>record3; for (int i = 0; i < 1000; i++) { if (record1[i] != 0 && record2[i] != 0) record3.push_back(i); } return record3; } }; int main() { vector<int> nums1 = { 4,9,5 }; vector<int> nums2 = { 9,4,9,8,4 }; Solution a; vector<int> nums3 = a.intersection(nums1, nums2); for(int i = 0 ;i<nums3.size();i++) cout <<nums3[i]<<' '; cout << endl; return 0; }
set哈希表
使用unordered_set进行哈希映射，统计数组出现的元素
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int> result; unordered_set<int> set1(nums1.begin() , nums1.end()); for (int i = 0; i < nums2.size(); i++) { if (set1.find(nums2[i]) != set1.end()) { result.insert(nums2[i]); } } return vector<int>(result.begin(), result.end()); } };
C++11写法 auto关键字
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int> result; unordered_set<int> set1(nums1.begin() , nums1.end()); for (auto num : nums2) { if (set1.find(num) != set1.end()) { result.insert(num); } } return vector<int>(result.begin(), result.end()); } };
二刷
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> my_set; vector<int> result; for(int i=0 ;i<nums1.size();i++) my_set.insert(nums1[i]); for(int i=0 ;i<nums2.size();i++) { if(my_set.find(nums2[i]) != my_set.end()) { my_set.erase(nums2[i]); result.push_back(nums2[i]); } } return result; } };
