专栏首页日常杂谈两个数组的交集

两个数组的交集

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接: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慢了一些,但是代码的简洁了很多,各有优缺点。

复杂度分析:

  • 时间复杂度:一般情况下是 O(m+n)O(m+n),最坏情况下是 O(m \times n)O(m×n)。
  • 空间复杂度:最坏的情况是 O(m+n)O(m+n),当数组中的元素全部不一样时。

只能说还是太菜。。。。。。。。

分享及成功:http:www.xbhog.cn

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/intersection-of-two-arrays

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • tk基础--标签、按钮

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    xbhog
  • (csdn)阅读数小程序v1.0

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    xbhog
  • 02-空间复杂度、递归

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    xbhog
  • 【leetcode刷题】T43-两个数组的交集

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

    木又AI帮
  • leetcode 4 Median of Two Sorted Arrays

    @坤的
  • [翻译]Bitmap的异步加载和缓存

    内容概述 [翻译]开发文档:android Bitmap的高效使用 本文内容来自开发文档“Traning > Displaying Bitmaps Effic...

    用户1172465
  • 如何对单行多次update接口进行压测

    在对服务端进行测试的时候,经常会遇到这类情况:单个接口的功能就是修改数据库中某一条数据某个字段的值。在对这类接口进行压测的过程中,遇到一个难点,如何每次都设置不...

    八音弦
  • jquery easyui datagrid mvc server端分页排序筛选的实现

    1自定义一个ModelBinder public class filterRule { public string field { g...

    阿新
  • Leetcode 739. Daily Temperatures

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • C++的引用与const指针的关系以及各种传递方式

    首先我们知道 const int *p 与 int const *p 是一样的,即 *p 是常量;而 int * const p 跟上面是不一样的,即 p 是常...

    s1mba

扫码关注云+社区

领取腾讯云代金券