leetcode 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.
题目地址:leetcode Intersection of Two Arrays
题意:给定两个数组,求他们的交集(不算重复)
思路:太TM水了,直接上哈希表即可。。。
Python 1
2
3
4
5
6
7
8
9
10
11
12
13class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
ans = []
nums1 = set(nums1)
for num in nums2:
if num in nums1:
ans.append(num)
return list(set(ans)) #remove duplicate
当然也可以one line
1 | class Solution(object): |
C++ 1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> vis;
unordered_set<int> intersection;
vector<int> ans;
for (int num : nums1) vis.insert(num);
for (int num : nums2) if (vis.find(num) != vis.end()) intersection.insert(num);
for (int num : intersection) ans.push_back(num);
return ans;
}
};
Java 1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> vis1 = new HashSet<Integer>();
HashSet<Integer> intersection = new HashSet<Integer>();
for(int num:nums1) vis1.add(num);
for(int num:nums2) if(vis1.contains(num)) intersection.add(num);
int []ans = new int[intersection.size()];
int i = 0;
for(int num:intersection)
ans[i++] = num;
return ans;
}
}
leetcode Intersection of Two Arrays II
Given two arrays, write a function to compute their intersection.
Example: Given nums1 =
[1, 2, 2, 1]
, nums2 =[2, 2]
, return[2, 2]
.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 num2'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?
题目地址:Intersection of Two Arrays II
题意:给定两个数组,求他们的交集(可以重复)
思路:用个字典。。。计数即可。
1 | class Solution(object): |
本题是leetcode 349 Intersection of Two Arrays 和 leetcode 350 Intersection of Two Arrays II题解
更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/