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 做

    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.