给你两个整数数组nums1
和nums2
,请你以数组形式返回数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。
示例:
输入:nums1 = [1, 2, 2, 1], nums2 = [2, 2]
输出:[2, 2]
思路一:排序+双指针
我们可以先将所给两个数组进行排序,之后用双指针遍历这两个有序序列,遍历过程如下:
- 若两个指针指向的元素不相等,则小的指针往后走。
- 若两个指针指向的元素相等,则该元素属于交集,两个指针同时往后走。
- 若其中一个序列走完了,则遍历结束。
代码一:
//排序+双指针
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
//1、将nums1和nums2分别进行排序
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
//2、使用双指针找出num1和nums2的交集
vector<int> vRet;
int len1 = nums1.size(), len2 = nums2.size();
int pos1 = 0, pos2 = 0;
while (pos1 < len1&&pos2 < len2)
{
if (nums1[pos1] < nums2[pos2]) //两个指针指向的元素不相等
{
pos1++; //小的往后走
}
else if (nums2[pos2] < nums1[pos1]) //两个指针指向的元素不相等
{
pos2++; //小的往后走
}
else //两个指针指向的元素相等
{
vRet.push_back(nums1[pos1]); //该元素属于交集
//两个指针一起往后走
pos1++;
pos2++;
}
}
return vRet;
}
};
思路二:哈希表
对于该题目,我们可以借助一个哈希表来求解,步骤分为两步:
- 将元素个数较少的数组先放入哈希表,统计出每个元素对应的出现次数。
- 遍历另一个数组,找出两个数组的交集。
遍历另一个数组,利用哈希表找两个数组的交集时,具体的查找方法如下:
- 如果遍历到的元素在哈希表中出现,则该元素属于交集,并将哈希表中该元素出现的次数减少一次,如果哈希表中该元素出现的次数减为0,则将该元素从哈希表中移除。
- 如果遍历到的元素没有在哈希表中出现,则继续遍历下一个元素。
这其实就是将一个数组当中的元素先用哈希表记录下来,然后遍历另一个数组的元素,对比哈希表当中的数据找到可以进行抵消的元素,可以抵消的元素即是这两个数组的交集。
说明一下:选择将元素个数较少的数组放入哈希表,可以降低空间复杂度。
代码二:
//哈希表
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
//为了降低空间复杂度,应该先将元素个数较少的数组放入哈希表
if (nums1.size() > nums2.size())
{
return intersect(nums2, nums1);
}
//1、将nums1中的每个数字以及对应出现的次数放入哈希表中
unordered_map<int, int> um;
for (auto e : nums1)
{
um[e]++;
}
//2、遍历nums2,找出nums1和nums2的交集
vector<int> vRet;
for (auto e : nums2)
{
if (um.count(e)) //该元素在哈希表中
{
vRet.push_back(e); //该元素属于交集
um[e]--; //减少该元素在哈希表中出现的次数
if (um[e] == 0) //该元素的次数已经变为0了
{
um.erase(e); //将该元素从哈希表中删除
}
}
}
return vRet;
}
};