题目描述

给定两个数组，编写一个函数来计算它们的交集。

示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]

示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明：

• 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
• 我们可以不考虑输出结果的顺序。

解题思路

为减少循环次数，选择长度较小的数组进行遍历，判断长度较大的数组中是否有此元素，如果有，则加入结果中，并在长度较大的数组中删除此元素。

代码

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        ans=[]
        l1=len(nums1)
        l2=len(nums2)
        if l1<=l2:
            for num in nums1:
                if num in nums2:
                    ans.append(num)
                    nums2.remove(num)
        else:
             for num in nums2:
                if num in nums1:
                    ans.append(num)
                    nums1.remove(num)
        return ans

结果

反思

目前执行速度最快的代码如下：

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        dictnums1 = dict()
        ans = []
        for num in nums1:
            dictnums1[num] = dictnums1[num] + 1 if num in dictnums1 else 1
        for num in nums2:
            if num in dictnums1 and dictnums1[num]>=1:
                ans.append(num)
                dictnums1[num] -=1
        return ans

其思路是建立一个以数组1中元素为键的字典，统计数组1中各个元素出现的次数，随后遍历数组2，若数组2中的数在数组1的字典键值中出现，则将其加入答案，并将数组1对应元素的计数减1。