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:
1.What if the given array is already sorted? How would you optimize your algorithm? 2.What if nums1's size is small compared to nums2's size? Which algorithm is better?
3.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?
和上一题I的区别在于这里的结果里要反映出重复元素。
最简单的还是直接用 hash table 做
def intersect(self, nums1, nums2):
hashmap = {}
for n in nums1:
hashmap[n] = hashmap.get(n, 0) + 1 # 使用 get(),在key不存在的时候不会出错
result = []
for n in nums2:
if hashmap.get(n, 0) > 0:
result.append(n)
hashmap[n] -= 1
return result
两根指针的做法：(这个可以作为 follow up 1 的回答)。要sort的话 O(N*logN + M*logM)，如果input已经sort过的话，O(N + M)
def intersection(self, nums1, nums2):
# write your code here
nums1.sort()
nums2.sort()
i = j = 0
result = []
while i < len(nums1) and j < len(nums2):
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
Follow up 2的回答应该是用binary search，程序在 LintCode TLE，在LeetCode可过。
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
nums1.sort()
nums2.sort()
if len(nums1) > len(nums2): # 要保证在长的里面找短的
nums1, nums2 = nums2, nums1
result = []
# follow up 2: binary search nums1[i] in nums2
i = 0
while i < len(nums1):
target = nums1[i]
k = self.binarySearch(nums2, target)
cnt = 1
while i < len(nums1) - 1 and nums1[i] == nums1[i+1]:
cnt += 1
i += 1
k = min(cnt, k)
if k > 0:
result = result + [target] * k
i += 1
return result
def binarySearch(self, nums, target): # 返回nums有多少个target，思路: findFirst, findLast, 个数 = last - first + 1
# return how many targets in nums
if not nums:
return 0
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = (start + end) // 2
if nums[mid] >= target:
end = mid
else:
start = mid
if nums[start] == target:
firstIdx = start
elif nums[end] == target:
firstIdx = end
else:
return 0
start, end = 0, len(nums) - 1
while start + 1 < end:
mid = (start + end) // 2
if nums[mid] <= target:
start = mid
else:
end = mid
lastIdx = end if nums[end] == target else start
return lastIdx - firstIdx + 1
Follow up 3, 在 LeetCode discuss 看到的讨论：
If only nums2 cannot fit in memory, put all elements of nums1 into a HashMap, read chunks of array that fit into the memory, and record the intersections.
If both nums1 and nums2 are so huge that neither fit into the memory, sort them individually (external sort), then read 2 elements from each array at a time in memory, record intersections.