First solution: not sure about the time complexity, anyone knows the complexity of dict.has_key?

Or we can choose the shorter array to do the search, which can save some time. This also answers the follow-up question #2.

Second solution, sort(). 52ms too. Of course, if the array is pre sorted, second solution saves a lot of time. This answers the follow-up question #1.

About the follow-up questions #3, solution 1 works well. We can save nums1 first, and check each element in nums2.

solution 1: using dict 52ms

```
def intersect(self, nums1, nums2):
import collections
dict1 = dict(collections.Counter(nums1))
res = []
for i in nums2:
if dict1.has_key(i):
if dict1[i] > 0:
dict1[i] -= 1
res.append(i)
return res
```

solution 2: sort() 52ms

```
def intersect(self, nums1, nums2):
nums1.sort()
nums2.sort()
res = []
i, j = 0, 0
while i < len(nums1) and j < len(nums2):
if nums1[i] == nums2[j]:
res.append(nums1[i])
i, j = i + 1, j + 1
elif nums1[i] < nums2[j]:
i += 1
else:
j += 1
return res
```