原文链接 [每日 LeetCode] 350. Intersection of Two Arrays II
Description:
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Note:
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
Follow up:
- What if the given array is already sorted? How would you optimize your algorithm?
- What if_nums1_’s size is small compared to_nums2_’s size? Which algorithm is better?
- What if elements of_nums2_are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
思路:本题是[每日 LeetCode] 349. Intersection of Two Arrays 的改进版,本题要求相同的元素全部返回,而 349 题只要求返回重复中的一个。有两种思路,如下:
-
思路一:使用 unordered_map 容器,对 num1 中的元素为 key 和出现的次数为 value 进行统计,然后遍历 num2,在 map 中查找,如找到则对应元素的 value 减一,直到遍历完成。
-
思路二:可以首先对两个数组进行排序,然后使用两个指针 i,j 同时从最小的数开始,如果相等则加入到 res 数组中,若指向 num1 的元素更大,则让 j+1,否则 i+1,直到两个指针到达最大值位置。
C++ 代码(思路一)
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> m;
vector<int> res;
for (auto a : nums1)
++m[a];
for (auto a : nums2) {
if (m[a]-- > 0)
res.push_back(a);
}
return res;
}
};
运行时间:8ms
运行内存:9.7M
C++ 代码(思路二)
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
int i = 0, j = 0;
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
while (i < nums1.size() && j < nums2.size()) {
if (nums1[i] == nums2[j]) {
res.push_back(nums1[i]);
++i; ++j;
} else if (nums1[i] > nums2[j]) {
++j;
} else {
++i;
}
}
return res;
}
};
运行时间:8ms
运行内存:8.8M
评论
发表评论
相关阅读
- [每日 LeetCode] 349. Intersection of Two Arrays
- [每日 LeetCode] 543. Diameter of Binary Tree
- [每日 LeetCode] 559. Maximum Depth of N-ary Tree
- [每日 LeetCode] 101. Symmetric Tree
随机阅读:
- [每日 LeetCode] 532. K-diff Pairs in an Array
- [每日 LeetCode] 665. Non-decreasing Array
- [每日 LeetCode] 840. Magic Squares In Grid
- [每日 LeetCode] 35. Search Insert Position
- [每日 LeetCode] 234. Palindrome Linked List
Description:
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Note:
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
Follow up:
- What if the given array is already sorted? How would you optimize your algorithm?
- What if nums1 's size is small compared to nums2 's size? Which algorithm is better?
- What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
思路:本题是[每日 LeetCode] 349. Intersection of Two Arrays 的改进版,本题要求相同的元素全部返回,而 349 题只要求返回重复中的一个。有两种思路,如下:
-
思路一:使用 unordered_map 容器,对 num1 中的元素为 key 和出现的次数为 value 进行统计,然后遍历 num2,在 map 中查找,如找到则对应元素的 value 减一,直到遍历完成。
-
思路二:可以首先对两个数组进行排序,然后使用两个指针 i,j 同时从最小的数开始,如果相等则加入到 res 数组中,若指向 num1 的元素更大,则让 j+1,否则 i+1,直到两个指针到达最大值位置。
C++ 代码(思路一)
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> m;
vector<int> res;
for (auto a : nums1)
++m[a];
for (auto a : nums2) {
if (m[a]-- > 0)
res.push_back(a);
}
return res;
}
};
运行时间:8ms
运行内存:9.7M
C++ 代码(思路二)
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
int i = 0, j = 0;
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
while (i < nums1.size() && j < nums2.size()) {
if (nums1[i] == nums2[j]) {
res.push_back(nums1[i]);
++i; ++j;
} else if (nums1[i] > nums2[j]) {
++j;
} else {
++i;
}
}
return res;
}
};
运行时间:8ms
运行内存:8.8M
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于