LeetCode 刷题 Swift 两个数组的交集

目录
  • 题目
  • 方法一：两个集合
    • 思路及解法
    • 代码
    • 复杂度分析
  • 方法二：排序 + 双指针
    • 思路及解法
    • 代码
    • 复杂度分析

题目

给定两个数组 nums1 和 nums2，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

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

输出： [2]

示例 2：

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

输出： [9,4]

解释： [4,9] 也是可通过的

方法一：两个集合

思路及解法

计算两个数组的交集，直观的方法是遍历数组 nums1，对于其中的每个元素，遍历数组 nums2 判断该元素是否在数组 nums2 中，如果存在，则将该元素添加到返回值。假设数组 nums1 和 nums2 的长度分别是 m 和 n，则遍历数组 nums1 需要 O(m) 的时间，判断 nums1 中的每个元素是否在数组 nums2 中需要 O(n) 的时间，因此总时间复杂度是 O(mn)。

如果使用哈希集合存储元素，则可以在 O(1)的时间内判断一个元素是否在集合中，从而降低时间复杂度。

首先使用两个集合分别存储两个数组中的元素，然后遍历较小的集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值。该方法的时间复杂度可以降低到 O(m+n)

代码

class Solution {
    func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        return set_intersection(Set(nums1), Set(nums2))
    }
    func set_intersection(_ set1: Set<Int>, _ set2: Set<Int>) -> [Int] {
        if set1.count > set2.count {
            return set_intersection(set2, set1)
        }
        var intersection: [Int] = []
        for num in set1 {
            if set2.contains(num) {
                intersection.append(num)
            }
        }
        return intersection
    }
}

复杂度分析

方法二：排序 + 双指针

思路及解法

如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。

首先对两个数组进行排序，然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的，为了保证加入元素的唯一性，我们需要额外记录变量 pre\textit{pre}pre 表示上一次加入答案数组的元素。

初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，且该数字不等于 pre\textit{pre}pre ，将该数字添加到答案并更新 pre\textit{pre}pre 变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

代码

class Solution {
    func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        let newNums1: [Int] = nums1.sorted()
        let newNums2: [Int] = nums2.sorted()
        let length1: Int = newNums1.count
        let length2: Int = newNums2.count
        var intersection: [Int] = []
        var index1 = 0
        var index2 = 0
        while index1 < length1 && index2 < length2 {
            let num1 = newNums1[index1]
            let num2 = newNums2[index2]
            if num1 == num2 {
                if intersection.isEmpty || num1 != intersection.last {
                    intersection.append(num1)
                }
                index1 += 1
                index2 += 1
            } else if num1 < num2 {
                index1 += 1
            } else {
                index2 += 1
            }
        }
        return intersection
    }
}

复杂度分析

以上就是LeetCode 刷题 Swift 两个数组的交集的详细内容，更多关于Swift 两个数组交集的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Swift4.0 Array数组详解

    数组的介绍 数组(Array)是一串有序的由相同类型元素构成的集合,数组中的集合元素是有序的,可以重复出现.在Swift中数组类型是Array,是一个泛型集合.数组分成:可变数组和不可变数组,分别使用let修饰的数组是不可变数组,使用var修饰的数组是可变数组. 数组的初始化 一.初始化一个空数组(类型:[数据类型]()) 1.创建一个整形的空数组 let  array = [Int] () 这里array 数组变量 被let 修辞 ,array数组是不可变数组,只能访问,不能修改 var  a

  • 探讨Swift数组和字典

    探讨Swift数组和字典

    数组是一个存储多个相同类型的值的有序列表.相同的值,可以在不同的位置出现在一个数组中的多个次. Swift数组是具体的.他不同于Objective-C的的NSArray和NSMutableArray里的类,它可以存储任何类型的对象,不提供有关它们返回的对象的性质的任何信息.在斯Swift,一个特定的数组可以存储的值类型总是明确的,无论是通过显式类型批注,或通过类型推断,而不一定是类类型.如果创建诠释值的数组,例如,你不能插入比Int值以外的任何值到该数组.Swift数组是类型安全的,并且总是清楚

  • 详解Swift中对C语言接口缓存的使用以及数组与字符串转为指针类型的方法

    详解Swift中对C语言接口缓存的使用以及数组与字符串转为指针类型的方法 由于Swift编程语言属于上层编程语言,而Swift中由于为了低层的高性能计算接口,所以往往需要C语言中的指针类型,由此,在Swift编程语言刚诞生的时候就有了UnsafePointer与UnsafeMutablePointer类型,分别对应为const Type*类型与Type *类型. 而在Swift编程语言中,由于一般数组(Array)对象都无法直接用于C语言中含有指针类型的函数参数(比如:void*),所以往往需要

  • Swift数组详细用法解析

    一.说明 Swift数组中的类型必须一致,这一点与OC不同 // 数组初始化 var numbers = [0,1,2,3,4,5] var vowels = ["A","E","I","O","U"] // 数组的类型: [Int] 或者 Array<Int> //var numbers: [Int] = [0,1,2,3,4,5] //var numbers: Array<Int>

  • Swift 4中一些实用的数组技巧小结

    前言 Swift提供了两种集合类型来存放多个值--数组(Array)和字典(Dictionary).这个大家应该都知道,在年前的时候,买了本Swift 进阶(swift4.0),过完年回来正在一点点学习,不得不说喵神写的东西还是不错的,￥69元对广大程序员来说已经不算啥了.如果感兴趣可以买一本,真心不错 当我从头来学习数组的时候发现好多函数真的太有用了,下面话不多说了,来一起看看详细的介绍吧. Swift 4.0 中的可变数组技巧 我们可用 Xcode 创建playground 来进行练习 首先

  • Swift 数组及常用方法详解总结

    目录 1. 创建数组 2. 快捷创建重复元素的数组 3. 数组相加 4. 常用方法 5. 数组遍历 Swift 数组及常用方法 1. 创建数组 // 创建整型数组 var array1: [Int] = [] // [] var arrya2: Array<Int> = [1, 2, 3] // [1, 2, 3] var arryaInt = [1, 2, 3] // [1, 2, 3] var array3 = Array(arrayLiteral: 1, 2, 3) // [1, 2,

  • LeetCode 刷题 Swift 两个数组的交集

    LeetCode 刷题 Swift 两个数组的交集

    目录 题目 方法一:两个集合 思路及解法 代码 复杂度分析 方法二:排序 + 双指针 思路及解法 代码 复杂度分析 题目 给定两个数组 nums1 和 nums2,返回 它们的交集 .输出结果中的每个元素一定是 唯一 的.我们可以 不考虑输出结果的顺序 . 示例 1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2] 示例 2: 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [9,4] 解释: [4,9] 也是可

  • 如何用C++制作LeetCode刷题小技巧-错题记录本

    一 . 刷题小技巧 1,c++中的for(auto a:b)用法 for(auto a:b)中b为一个容器,效果是利用a遍历并获得b容器中的每一个值,但是a无法影响到b容器中的元素. for(auto &a:b)中加了引用符号,可以对容器中的内容进行赋值,即可通过对a赋值来做到容器b的内容填充. 2,c++中map的元素进行按照值排序(默认按照键排序) 为什么不能对map进行按值排序呢?因为sort排序只能对线性结构进行排序,而map是采用红黑树的数据结构. 一是通过将map转换到序列容器,再用

  • 如何在Intellij中安装LeetCode刷题插件方便Java刷题

    一.安装 在 IDEA(2019)的 setting 的 Plugins 的 Marketplace 中搜索 leetcode,即可以找到该插件,安装完成了,重启即可. 二.配置 1.重启完成后,第一次使用的时候,需要一些基本的配制,在 setting 中的 Tools 中可以找到该插件工具,为 leetcode plugin,在里面,可以选择访问的为国际的 LeetCode 还是国内的,以及何种语言,同时,输入自己账户名(LoginName)和密码(Password),则可以和自己帐号关联起来

  • JS计算两个数组的交集、差集、并集、补集（多种实现方式）

    方法一:最普遍的做法 使用 ES5 语法来实现虽然会麻烦些,但兼容性最好,不用考虑浏览器 JavaScript 版本.也不用引入其他第三方库. 1,直接使用 filter.concat 来计算 var a = [1,2,3,4,5] var b = [2,4,6,8,10] //交集 var c = a.filter(function(v){ return b.indexOf(v) > -1 }) //差集 var d = a.filter(function(v){ return b.index

  • Python3实现计算两个数组的交集算法示例

    本文实例讲述了Python3实现计算两个数组的交集算法.分享给大家供大家参考,具体如下: 问题: 给定两个数组,写一个方法来计算它们的交集. 方案一:利用collections.Counter的&运算,一步到位,找到 最小次数 的相同元素. # -*- coding:utf-8 -*- #! python3 def intersect(nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :r

  • JavaScript实现两个数组的交集

    目录 两个数组的交集 I 两个数组的交集 II 两个数组的交集 I 给定两个数组 ​​nums1​​​ 和 ​​nums2​​ ,返回 它们的交集 .输出结果中的每个元素一定是 唯一 的.我们可以 不考虑输出结果的顺序 . 示例 1: 输入:nums1 = [1,2,2,1], nums2 = [2,2]输出:[2] 示例 2: 输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出:[9,4]解释:[4,9] 也是可通过的 注: 1 <= nums1.length,

  • js取两个数组的交集|差集|并集|补集|去重示例代码

    复制代码 代码如下: /** * each是一个集合迭代函数,它接受一个函数作为参数和一组可选的参数 * 这个迭代函数依次将集合的每一个元素和可选参数用函数进行计算,并将计算得的结果集返回 {%example <script> var a = [1,2,3,4].each(function(x){return x > 2 ? x : null}); var b = [1,2,3,4].each(function(x){return x < 0 ? x : null}); alert

  • 使用go语言实现查找两个数组的异同操作

    使用go语言实现查找两个数组的异同操作

    最近项目上碰到个小需求,输入是两个数组,一个旧数组一个新数组,要求获取新数组相对旧数组所有新增和删除的元素,例如: 输入: arr_old: {"1", "2", "4", "5", "7", "9"} arr_new: {"2", "3", "4", "6", "7"} 返回: arr_

  • vscode中配置LeetCode插件的教程(愉快刷题)

    大家好,今早在B站看到up主的vscode里藏了leetcode插件,这才知道原来还有这款神器.但是没想到在用的时候遇到了一些麻烦,花了一点时间才解决.所以写这篇文章除了给大家安利这个好用的插件之外,也是为了帮助更多的同学避免踩坑. 简介vscode vscode在工业界鼎鼎大名,被誉为微软少有的拿得出手的精品(逃).原本是不想过多赘述的,但是鉴于许多粉丝还是正在上学的萌新,所以花点笔墨简单介绍一下. vscode是微软开发的编辑器,严格说起来它并不是一个IDE,只是一个编辑器.但是由于它支持嵌

  • IntelliJ IDEA 刷题利器 LeetCode 插件详解

    IDEA整合LeetCode插件,可以在 IDEA 本地编辑代码并且运行提交,还能关联自己的账号,非常实用. 下载安装 配置 点击File->Settings->Tools->leetcode plugin,如图: 参数说明: Custom code template: 开启使用自定义模板,否则使用默认生成格式 CodeFileName: 生成文件的名称,默认为题目标题 CodeTemplate: 生成题目代码的内容,默认为题目描述和题目代码 TemplateConstant: 模板常用

随机推荐