LeetCode 349. Intersection of Two Arrays(两个数组的交集)
题目描述
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1]
, nums2 = [2, 2]
, return [2]
.
Note:
- Each element in the result must be unique.
- The result can be in any order.
解法一
思路
“交集”即同时出现在两个数组中的元素的集合。那么如何来判断“元素同时出现在两个数组中”呢?实际只需要遍历其中一个数组,对其每个元素检查其是否在另一个数组中,为了加快这个“检查”的速度,不妨把另一个数组首先转换为HashMap,这样每次“检查”的时间复杂度就只有O(1)了。
接下来还有一个问题,如果两个数组中含有重复元素的话该如何处理呢?根据此题题意,输出的交集中应该不含有重复元素,那么遍历的过程中,中间结果也用HashMap保存就好了,这样可以剔除重复元素。
Python
class Solution:
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1_set = set(nums1)
intersect = set()
for num in nums2:
if num in nums1_set:
intersect.add(num)
return list(intersect)
Java
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> nums1Set = new HashSet<>();
for (int num : nums1) {
nums1Set.add(num);
}
Set<Integer> intersect = new HashSet<>();
for (int num : nums2) {
if (nums1Set.contains(num)) {
intersect.add(num);
}
}
int[] intersectArray = new int[intersect.size()];
int i = 0;
for (int num : intersect) {
intersectArray[i++] = num;
}
return intersectArray;
}
}
C++
class Solution {
public:
vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
set<int> nums1Set(nums1.begin(), nums1.end());
set<int> intersect;
for (int num : nums2) {
if (nums1Set.find(num) != nums1Set.end()) {
intersect.insert(num);
}
}
return vector<int>(intersect.begin(), intersect.end());
}
};