两个set法
最直观最简单的解法，set一般用于检查某元素是否存在于某个集合中。并且它能提供O(1)的时间复杂度
算法过程
- 利用set对数组去重
- 遍历查找长度较短的set去对比另外个set，检查是否有重合元素
- 将重合元素存入数组result中
代码
class Solution:
def set_intersection(self, set1, set2):
return [x for x in set1 if x in set2]
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
s1 = set(nums1)
s2 = set(nums2)
if len(nums1) < len(nums2):
return self.set_intersection(s1, s2)
else:
return self.set_intersection(s2, s1)
复杂度分析
- 时间复杂度: O(M+N)
- 空间复杂度: O(M+N)
二分查找法
这个解法算是解法1的变招，其实思路还是一样的, 只不过用二分查找去替换set的功能。当然因为要用二分查找，先对数组排序是必然的。在这里它的时间复杂度为O(logn)
然后遍历较短的数组，通过二分查找来找到重复的元素。
这个解法其实效率不高，不是很推荐。
代码
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
nums1 = sorted(nums1)
nums2 = sorted(nums2)
res = []
if len(nums1) < len(nums2):
for i in nums1:
if(self.binarySearch(nums2, i) is not None): res.append(i)
else:
for i in nums2:
if(self.binarySearch(nums1, i) is not None): res.append(i)
return set(res)
def binarySearch(self, nums, target):
start = 0
high = len(nums) -1
while start <= high:
mid = (start + high)//2
guess = nums[mid]
if guess == target: return guess
if guess < target: start = mid + 1
else: high = mid -1
return None
复杂度分析
- 时间复杂度: O(NlogN)
- 空间复杂度: O(NlogN)