0%

leetcode 349 Intersection of Two Arrays || leetcode 350 Intersection of Two Arrays II

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
13
class 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
2
3
4
5
6
7
8
class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
return list(set(nums1) & set(nums2))

C++

1
2
3
4
5
6
7
8
9
10
11
12
class 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
13
class 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
ans = []
nums1 = collections.Counter(nums1)
for x in nums2:
if x in nums1:
ans.append(x)
nums1[x] -= 1
if nums1[x] == 0:
del nums1[x]
return ans

 

本题是leetcode 349 Intersection of Two Arrays  和 leetcode 350 Intersection of Two Arrays II题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~