LeetCode349 Intersection of Two Arrays

文章目录
  1. 1. 描述
  2. 2. 样例
  3. 3. 思路
  4. 4. 代码

描述

Given two arrays, write a function to compute their intersection.

Note:

  • Each element in the result must be unique.
  • The result can be in any order.

样例

1
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

思路

求两个数组的交集。注意答案中不能有重复的元素。

二分:
先对nums1排序,然后遍历nums2中每个元素,对每个元素用二分查找是否存在于nums1中,去重可用map维护。

双指针:
对nums1和nums2都排序,当双指针指向相同的数时加到答案里即可。

代码

二分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
map<int, bool> hashTable;
vector<int> ans;
for (auto x: nums2) {
auto iter = lower_bound(nums1.begin(), nums1.end(), x);
if (iter != nums1.end() && *iter == x && !hashTable.count(x)) {
ans.push_back(x);
hashTable[x] = true;
}
}
return ans;
}
};

双指针:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
map<int, bool> hashTable;
vector<int> ans;
int n = nums1.size(), m = nums2.size(), i = 0, j = 0;
while (i < n && j < m) {
if (nums1[i] < nums2[j]) i++;
else if (nums1[i] > nums2[j]) j++;
else {
if (!hashTable.count(nums1[i])) ans.push_back(nums1[i]);
hashTable[nums1[i]] = true;
i++; j++;
}
}
return ans;

}
};

优雅的实现:

1
2
3
4
5
6
7
8
9
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> s(nums1.begin(), nums1.end());
vector<int> ans;
for (auto x: nums2) if (s.erase(x)) ans.push_back(x);
return ans;
}
};

分享到 评论