样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2].要求去重,这样还是稍微有点难度。
最暴力的方法,对于nums1种的每个元素都去nums2种搜索,看是否存在,如果存在,就把这个数放入结果中,因为要求去重,所以放入的时候还要检查一下是否已经存在,我们可以先对两个数组都进行排序来规避这个问题,显然太暴力了,都懒得写,时间估计肯定超时了。
先排序,然后利用双指针把两个数组种都有的数放入res,除了第一次,每次放入的时候检查一下和上一次放入的是否是相同的,如果是相同的就不再放入了。 我也不知道这个怎么会超时:
vector<int> intersection(vector<int> nums1, vector<int> nums2) { if(nums1.empty()||nums2.empty()) return vector<int>(); vector<int> res1; //vector<int> res; sort(nums1.begin(),nums1.end()); sort(nums2.begin(),nums2.end()); int n1,n2; for(n1=0,n2=0;n1<nums1.size()&&n2<nums2.size();) { if(nums1[n1]==nums2[n2]) { if(res1.size()==0||*(res1.end()-1)!=nums1[n1]) res1.push_back(nums1[n1]); n1++; n2++; } else if(nums1[n1]<nums2[n1]) n1++; else if(nums2[n2]<nums1[n1]) n2++; } return res1; // write your code here }
依次把所有的数都放入set中(就是去重,排序过的),然后利用双指针遍历即可,这个就相当esay了。
vector<int> intersection(vector<int> nums1, vector<int> nums2) { set<int> res1; set<int> res2; vector<int> res; for(auto n:nums1) { res1.insert(n); } for(auto n:nums2) { res2.insert(n); } auto beg1=res1.begin(); auto beg2=res2.begin(); auto end1=res1.end(); auto end2=res2.end(); for(;beg1!=end1&&beg2!=end2;) { if(*beg1==*beg2) { res.push_back(*beg1); beg1++; beg2++; } else if(*beg1<*beg2) { beg1++; } else if(*beg1>*beg2) { beg2++; } } return res; }
over!
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句