leetcode249,利用了STL中的set
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> n1(nums1.begin(),nums1.end()); set<int> n2; for(int i=0;i<nums2.size();i++) { if(n1.find(nums2[i])!=n1.end()) { n2.insert(nums2[i]); } } return vector<int> results(n2.begin(),n2.end()); } };
思路:set中的元素不重复,利用这一点方便进行最后的插入操作而不用去重。实际上第一个set<int> n1是没有必要的,可以直接vector来查找,但是用set的效率会更高。
下面给出用vector和库里面的find实现的方式:
1 class Solution { 2 public: 3 vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { 4 5 set<int> n2; 6 7 for(int i=0;i<nums2.size();i++) 8 { 9 auto it=nums1.end(); 10 if((it=find(nums1.begin(),nums1.end(),nums2[i]))!=nums1.end()) 11 { 12 n2.insert(nums2[i]); 13 } 14 } 15 16 return vector<int> (n2.begin(),n2.end()); 17 } 18 19 };vector实现
虽然每次创建一个迭代器会耗费内存,总体来说少了一个map会比较折中。
leetcode 250,利用了STL中的map。
class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { map<int,int> n1; for(int i=0;i<nums1.size();i++) { n1[nums1[i]]++; } vector<int> results; for(int i=0;i<nums2.size();i++) { if(n1[nums2[i]]>0) { results.push_back(nums2[i]); n1[nums2[i]]--; } } return results; } };
思路:因为要统计频率,题目要求不去重,所以需要统计元素出现频率。但又不知道集合中元素的大小,故无法用数组,所以采用map。