350.md

350. Intersection of Two Arrays II

难度: Easy

刷题内容

原题连接

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

内容描述

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

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
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:

What if the given array is already sorted? How would you optimize your algorithm?
What if nums1's size is small compared to nums2's size? Which algorithm is better?
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?

解题方案

思路 1 - 时间复杂度: O(NlgN) - 空间复杂度: O(1)

sort之后用双指针， beats 67.28%

class Solution:
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort()
        nums2.sort()
        p1, p2, res = 0, 0, []
        
        while p1 < len(nums1) and p2 < len(nums2):
            if nums1[p1] < nums2[p2]:
                p1 += 1
            elif nums1[p1] > nums2[p2]:
                p2 += 1
            else:
                res.append(nums1[p1])
                p1 += 1
                p2 += 1
        return res

思路 2 - 时间复杂度: O(m + n) - 空间复杂度: O(m + n)

一行版本，beats 98.43%

class Solution:
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        import collections
        return list((collections.Counter(nums1) & collections.Counter(nums2)).elements())

我还是不想使用Counter

class Solution:
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        lst = []
        dic = {}
        for n in nums1:
            if n not in dic:
                dic[n] = 1
            else:
                dic[n] += 1
        for n in nums2:
            if n in dic and dic[n] > 0:
                dic[n] -= 1
                lst.append(n)
        return lst