> For the complete documentation index, see [llms.txt](https://loghead.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://loghead.gitbook.io/algorithm-notes/array-matrix-interval-binary-indexed-tree/intersection-of-two-arrays-ii.md).

# Intersection of Two Arrays II

> Given two arrays, write a function to compute their intersection.
>
> Example:
>
> Given nums1 = \[1, 2, 2, 1], nums2 = \[2, 2], return \[2, 2].
>
> Note:
>
> 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 做

```python
    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)

```python
    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可过。

```python
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.