力扣算法：两个数组的交集

• 一、两个数组的交集
• • 1、问题
  • 2、思路
  • 3、代码
  • 4、时间与空间复杂度
• 备注

一、两个数组的交集

1、问题

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

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]

说明：

• 输出结果中的每个元素一定是唯一的。
• 我们可以不考虑输出结果的顺序。

2、思路

思路一：

1、对两个数组去重。
2、建立一个空数组用来存放“交集”。
3、遍历 “较长的数组” ，如果遍历到的元素 “在较短数组中” 并且 “不在交集数组中”，则将此元素添加到 “交集” 数组中。
4、返回 “交集” 数组。

思路二：

对两数组 “去重” - “取交集” - “转换为数组”。

3、代码

1、解题代码

#coding:utf-8
from typing import List
class Solution:
    def intersection1(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1,nums2 = set(nums1),set(nums2)
        def intersection(a, b):
            a_b = []
            for i in a:
                if (i in b) and (i not in a_b):
                    a_b.append(i)
            return a_b
        return intersection(nums1,nums2) if len(nums1) > len(nums2) else intersection(nums2,nums1)

    def intersection2(self, nums3: List[int], nums4: List[int]) -> List[int]:
        return list(set(nums3) & set(nums4))


if __name__ == "__main__":
    # nums1 = [4, 9, 5]
    # nums2 = [9, 4, 9, 8, 4]

    nums1 = [1, 2, 2, 1]
    nums2 = [2, 2]
    
    sl = Solution()
    print(sl.intersection1(nums1, nums2))
    print(sl.intersection2(nums1, nums2))

4、时间与空间复杂度

时间复杂度：O(N)
N为较长数组的长度。

空间复杂度：O(1)

备注

1、问题来自：

力扣（LeetCode）
https://leetcode-cn.com/problems/intersection-of-two-arrays