Leetcode 350. Intersection of Tw

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

Intersection of Two Arrays II

2. Solution

• Version 1

class Solution:
    def intersect(self, nums1, nums2):
        nums1.sort()
        nums2.sort()
        m = len(nums1)
        n = len(nums2)
        i = 0
        j = 0
        result = []
        while i < m and j < n:
            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

• Version 2

class Solution:
    def intersect(self, nums1, nums2):
        stat = {}
        result = []

        for x in nums1:
            stat[x] = stat.get(x, 0) + 1

        for x in nums2:
            if x in stat and stat[x] > 0:
                result.append(x)
                stat[x] -= 1
        return result

• Version 3

class Solution:
    def intersect(self, nums1, nums2):
        result = []
        nums2.sort()
        for num in nums1:
            index = binarySearch(nums2, num)
            if index is not None:
                result.append(num)
                nums2.pop(index)
        return result


def binarySearch(nums, target):
    left = 0
    right = len(nums) - 1
    while left <= right:
        middle = (left + right) // 2
        if nums[middle] == target:
            return middle
        elif nums[middle] > target:
            right = middle - 1
        else:
            left = middle + 1
    return None

Reference

1. https://leetcode.com/problems/intersection-of-two-arrays-ii/