Leetcode 350. Intersection of Two Arrays II

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Intersection of Two Arrays II

2. Solution

  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def intersect(self, nums1, nums2):
nums1.sort()
nums2.sort()
m = len(nums1)
n = len(nums2)
i = 0
j = 0
result = []
while i < m and j < n:
if nums1[i] < nums2[j]:
i += 1
elif nums1[i] > nums2[j]:
j += 1
else:
result.append(nums1[i])
i += 1
j += 1
return result
  • Version 2
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def intersect(self, nums1, nums2):
stat = {}
result = []
for x in nums1:
stat[x] = stat.get(x, 0) + 1
for x in nums2:
if x in stat and stat[x] > 0:
result.append(x)
stat[x] -= 1
return result
  • Version 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def intersect(self, nums1, nums2):
result = []
nums2.sort()
for num in nums1:
index = binarySearch(nums2, num)
if index is not None:
result.append(num)
nums2.pop(index)
return result
def binarySearch(nums, target):
left = 0
right = len(nums) - 1
while left <= right:
middle = (left + right) // 2
if nums[middle] == target:
return middle
elif nums[middle] > target:
right = middle - 1
else:
left = middle + 1
return None

Reference

  1. https://leetcode.com/problems/intersection-of-two-arrays-ii/
如果有收获,可以请我喝杯咖啡!