NC313 两个数组的交集
- 题目
- 题解(19)
- 讨论(7)
- 排行
- 面经
new
简单 通过率：29.64% 时间限制：1秒 空间限制：256M
知识点二分哈希排序双指针
描述
给定两个整数数组分别为𝑛𝑢𝑚𝑠1nums1, 𝑛𝑢𝑚𝑠2nums2，找到它们的公共元素并按返回。
数据范围：
1≤𝑛𝑢𝑚𝑠1.𝑙𝑒𝑛𝑔𝑡ℎ,𝑛𝑢𝑚𝑠2.𝑙𝑒𝑛𝑔𝑡ℎ≤10001≤nums1.length,nums2.length≤1000
1≤𝑛𝑢𝑚𝑠1[𝑖],𝑛𝑢𝑚𝑠2[𝑖]≤10001≤nums1[i],nums2[i]≤1000
思路：
法一：用两个set先对两个数组去重，然后对其中一个set进行遍历，每个元素去另一个set里面找。
法二：对两个数组从小到大排序，然后两个指针分别指向两个数组头部，依次比较，注意去重。
法三：本题数字变化比较小，因此可以用一个bool类型数组，下标表示以下标为元素是否出现在nums1中。然后在nums2中找是否出现过即可，注意去重的方法可以是第一次找到后改为false。
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums1 int整型vector * @param nums2 int整型vector * @return int整型vector*/vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// write code here// sort(nums1.begin(),nums1.end());// sort(nums2.begin(),nums2.end());// int r1=nums1.size(),r2=nums2.size();// int l1=0,l2=0;// vector<int>ret;// while(l1<r1&&l2<r2)// {// if(nums1[l1]<nums2[l2])// {// l1++;// }// else if(nums1[l1]>nums2[l2])// {// l2++;// }// else {// //判断是否重复// if(ret.size()==0||ret.back()!=nums1[l1])// ret.push_back(nums1[l1]);// l1++,l2++;// }// }// return ret;// set<int>hash;// set<int>hash1;// for(auto e:nums1)// {// hash.insert(e);// }// for(auto e:nums2)// {// hash1.insert(e);// }// vector<int>ret;// for(auto e:hash1)// {// if(hash.count(e))// {// ret.push_back(e);// }// }// return ret;vector<bool>hash(1001);for(auto e:nums1){hash[e]=true;}vector<int>ret;for(auto e:nums2) {if(hash[e]){hash[e]=false;ret.push_back(e);}}return ret;}
};
