Description
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Solution
最简单但是
Time complexity :
O(n + m) in the average case
O(n×m) in the worst case
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)))
Time： O(N+M)
class Solution:
def set_intersection(self, set1, set2):
return [x for x in set1 if x in set2]
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
set1 = set(nums1)
set2 = set(nums2)
if len(set1) < len(set2):
return self.set_intersection(set1, set2)
else:
return self.set_intersection(set2, set1)
class Solution(object):
def find_intersect(self,a,b):
'''
len a <= len b
'''
return [i for i in a if i in b ]
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
set1 = set(nums1)
set2 = set(nums2)
if len(set1) < len(set2):
return self.find_intersect(set1,set2)
else:
return self.find_intersect(set2,set1)
