forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
intersection-of-two-arrays.py
107 lines (89 loc) · 2.63 KB
/
intersection-of-two-arrays.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
# Time: O(m + n)
# Space: O(min(m, n))
# 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.
# Hash solution.
class Solution(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
if len(nums1) > len(nums2):
return self.intersection(nums2, nums1)
lookup = set()
for i in nums1:
lookup.add(i)
res = []
for i in nums2:
if i in lookup:
res += i,
lookup.discard(i)
return res
def intersection2(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
return list(set(nums1) & set(nums2))
# Time: O(max(m, n) * log(max(m, n)))
# Space: O(1)
# Binary search solution.
class Solution2(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
if len(nums1) > len(nums2):
return self.intersection(nums2, nums1)
def binary_search(compare, nums, left, right, target):
while left < right:
mid = left + (right - left) / 2
if compare(nums[mid], target):
right = mid
else:
left = mid + 1
return left
nums1.sort(), nums2.sort()
res = []
left = 0
for i in nums1:
left = binary_search(lambda x, y: x >= y, nums2, left, len(nums2), i)
if left != len(nums2) and nums2[left] == i:
res += i,
left = binary_search(lambda x, y: x > y, nums2, left, len(nums2), i)
return res
# Time: O(max(m, n) * log(max(m, n)))
# Space: O(1)
# Two pointers solution.
class Solution3(object):
def intersection(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1.sort(), nums2.sort()
res = []
it1, it2 = 0, 0
while it1 < len(nums1) and it2 < len(nums2):
if nums1[it1] < nums2[it2]:
it1 += 1
elif nums1[it1] > nums2[it2]:
it2 += 1
else:
if not res or res[-1] != nums1[it1]:
res += nums1[it1],
it1 += 1
it2 += 1
return res