两个数组的交集

xbhog

发布于 2019-10-22 17:46:20

1.6K0

发布于 2019-10-22 17:46:20

文章被收录于专栏：开发技能乱炖开发技能乱炖

本文链接：https://blog.csdn.net/weixin_43908900/article/details/102591900

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

示例 1:

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

示例 2:

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

说明：

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

首先说一下我自己的(菜鸡)思路：我先是想先去重第第一个数组(nums1)，然后循环判断值是否在nums2中，有的话，添加新的列表中。

代码实现如下例1：

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        num1 = set(nums1)
        num = [i for i in num1 if i in nums2]
        return num

还有一种类似的方法例2：

class Solution:
    def set_intersection(self, set1, set2):
        return [x for x in set1 if x in set2]
        
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """  
        set1 = set(nums1)
        set2 = set(nums2)
        
        if len(set1) < len(set2):
            return self.set_intersection(set1, set2)
        else:
            return self.set_intersection(set2, set1)

但是他的运行时间：

比我自己做快了24ms,值得深思问题，复杂度分析，

时间复杂度：O(m+n)O(m+n)，其中 n 和 m 是数组的长度。O(n)O(n) 的时间用于转换 nums1 在集合中，O(m)O(m) 的时间用于转换 nums2 到集合中，并且平均情况下，集合的操作为 O(1)O(1))
空间复杂度：O(m+n)O(m+n)，最坏的情况是数组中的所有元素都不同。

对于无所不能的python 来说，内置了交集方法，看看下面的操作例3：

class Solution:
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """  
        set1 = set(nums1)
        set2 = set(nums2)
        return list(set2 & set1)

怎样是不是有点无语，看看他的运行时间，虽然运行速度比上面例2慢了一些，但是代码的简洁了很多，各有优缺点。