Intersection of Two Arrays 两数组的交

Given two arrays, write a function to compute their intersection.

Example: Givennums1=[1, 2, 2, 1],nums2=[2, 2], return[2].

Note:

• Each element in the result must be unique.

• The result can be in any order.

python 自带功能：

    def intersection(self, nums1, nums2):
        return list(set(nums1) & set(nums2))

自己写个程序实现集合的交集功能：

    def intersection(self, nums1, nums2):
        s = set(nums1)
        result = set()        # 做成 set，避免重复元素
        for n in nums2:
            if n in s:
                result.add(n)

        return list(result)   # 题目要求返回数组，所以转回list

这样写也行

    def intersection(self, nums1, nums2):
        s = set(nums1)
        result = []          #直接做成 list
        for n in nums2:
            if n in s:
                result.append(n)
                s.remove(n)  # 在原来的集合里删掉n，避免 n 被重复放入 result

        return result

以上都是 O(N + M)。

还可以把两个数组排序后用2根指针，这是 O(NlogN)

    def intersection(self, nums1, nums2):
        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      # 这里 +1，下面的 while 循环，数组下表不会小于0
                j += 1
                while i < len(nums1) and nums1[i] == nums1[i - 1]:  # 跳过重复的数
                    i += 1
                while j < len(nums2) and nums2[j] == nums2[j - 1]:
                    j += 1

        return result

还有可以用2分法。排序一个数组，然后在这个数组里面找另外一个数组的数

class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort()
        nums2.sort()           # 数组2 排序主要是为了去重。如果用 set 来去重，数组2可以不排序
        result = []
        for i in xrange(len(nums2)):
            if i > 0 and nums2[i] == nums2[i - 1]:
                continue
            if self.binarySearch(nums1, nums2[i]):
                result.append(nums2[i])

        return result

    def binarySearch(self, array, target):
        if not array:
            return False

        start, end = 0, len(array) - 1
        while start + 1 < end:
            mid = (start + end) // 2
            if array[mid] == target:
                return True
            elif array[mid] < target:
                start = mid
            else:
                end = mid

        return array[start] == target or array[end] == target