返回两数组的交

2019-11-08 01:03:44

字体：大中小

来源：转载

供稿：网友

题目要求：返回两数组的交，同样的数字不能出现。如A = [1,2,2,1,]; B= [ 2,2];则answer = [2]

1.1 version one

由于第一次编写C++程序，采样最原始的方法，将数组2中的每个元素在数组一中进行遍历查找。预处理是将两数组分别排序并删除重复元素。

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { // Write your code here vector<int> nums_out; vector<int>::iterator it1; vector<int>::iterator it2; sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end()); nums1.erase(unique(nums1.begin(), nums1.end()), nums1.end()); nums2.erase(unique(nums2.begin(), nums2.end()), nums2.end()); for (it2 = nums2.begin(); it2 != nums2.end(); it2++) { for (it1 = nums1.begin(); it1 != nums1.end(); it1++) { if (*it2 == *it1) { nums_out.push_back(*it1); break; } } } return nums_out; }

1.2 version two

既然对两个数组都同时进行了排序，那么就可以用两个指针或者迭代器分别指向两个数组，对指针指向的两个数组分别进行大小比较，如果的哥数大，第二个指针+1，反之则第一个指针+1，知道出现相等，将当前数存储并将两个指针都+1；这样复杂度就变为o(nlgn) $o(nlgn)$

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { // Write your code here vector<int> nums_out; vector<int>::iterator it1; vector<int>::iterator it2; //sort(nums1,nums1.begin(), nums1.end()); sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end()); //vecSrc.erase(unique(vecSrc.begin(), vecSrc.end()), vecSrc.end()); nums1.erase(unique(nums1.begin(), nums1.end()), nums1.end()); nums2.erase(unique(nums2.begin(), nums2.end()), nums2.end()); it1 = nums1.begin(); it2 = nums2.begin(); //int temp = 0; while (it1 < nums1.end() && it2 < nums2.end()) { if (*it1 < *it2) it1++; else if (*it2 < *it1) it2++; else { nums_out.push_back(*it1); it1++; it2++; } } return nums_out; }};

1.3 version three

既然要对两个数组进行遍历就能知道两个数组中的数的大小，那么理想情况下的时间复杂度应该为o(n) $o(n)$ ;

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { // Write your code here vector<int> nums_out; vector<int> nums_result; nums_out.insert(nums_out.end(), nums1.begin(), nums1.end()); nums_out.insert(nums_out.end(), nums2.begin(), nums2.end()); sort(nums_out.begin(), nums_out.end()); vector<int>::iterator iter; iter = nums_out.begin(); while ( *(iter + 1) != *iter ) { iter++; } nums_result.push_back(*iter); for (; iter != nums_out.end() - 1; iter++) { if (*(iter + 1) == *iter) { continue; } else { nums_result.push_back(*(iter+1)); } } return nums_result; } //错误的理解了题目的意思，得出了错误的结论

1.4 version four

采用set容器里面的set_intersection函数：

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> s1(nums1.begin(), nums1.end()), s2(nums2.begin(), nums2.end()), res; set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(res, res.begin())); return vector<int>(res.begin(), res.end());}

1.5 version five

class Solution {public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> s(nums1.begin(), nums1.end()), res; for (auto a : nums2) { if (s.count(a)) res.insert(a); } return vector<int>(res.begin(), res.end()); }};

上一篇：FLV格式分析

下一篇：Unity常用设计模式之单例模式