Swift 两个数组的交集 II - LeetCode

两个数组的交集 II

给定两个数组,写一个方法来计算它们的交集。 例如: 给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

注意: 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。 我们可以不考虑输出结果的顺序。 跟进:

如果给定的数组已经排好序呢?你将如何优化你的算法? 如果 nums1 的大小比 nums2 小很多,哪种方法更优? 如果nums2的元素存储在磁盘上,内存是有限的,你不能一次加载所有的元素到内存中,你该怎么办?

双重循环数组,用record数组记录第二个数组中已经和第一个数组相等的元素的下标,在第二层循环中得到相等则判断record中有没有相等的下标,如果有则break。如果没有则该元素为交集元素,同时记录下标,然后break(不然会导致错误比如:[1],[1,1]->[1,1])。

class Solution {
    func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        var intersects = [Int]()
        var record = [Int]()
        for i in 0..<nums1.count {
            let temp = nums1[i]
            for j in 0..<nums2.count {
                if temp == nums2[j] {
                    var exist = false
//                     使用系统的contains()也是可以的
//                     if record.contains(j) {
//                         exist = true
//                         break
//                     }
                    for k in 0..<record.count {
                        if j == record[k] {
                           exist = true
                           break
                        }
                    }
                    if !exist {
                        record.append(j)
                        intersects.append(temp)
                        break
                    }
                    
                }
            }
        }
        return intersects
    }
}

跟进

1.有序,当s_nums[i] == l_nums[j] 时,,因为有序,i + 1,j + 1,同时记录下j + 1,当循环完l_nums时,下一次循环直接从k开始

代码如下:

func intersectSorted(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
//    print(3,Date().timeIntervalSince1970)
        var intersects = [Int]()

        var i = 0
        var j = 0
        var k = 0
        while i < nums1.count {
            while j < nums2.count && i < nums1.count {
                if nums1[i] == nums2[j] {
                    intersects.append(nums1[i])
                    i += 1
                    j += 1
                    k = j
                }
                j += 1
            }
            i += 1
            j = k
        }
//        print(4,Date().timeIntervalSince1970)
        return intersects
}

用两个函数计算同一有序的交集

intersect([1,1,1,1,2,2,12], [1,1,2,2,2,2,12])
intersectSorted([1,1,1,1,2,2,12], [1,1,2,2,2,2,12])

结果:
1 1522504932.52009
2 1522504932.52324
3 1522504932.52373
4 1522504932.52617

优化钱耗时:3.15ms
优化后耗时:2.24ms
快了:0.91ms

这只是一个单一的测试。。。貌似是变快了。。。???

2)。。。布吉岛 3)。。。布吉岛

用Swift开始学习算法中,在LeetCode中开始做初级算法这一章节,将做的题目在此做个笔记吧。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Jed的技术阶梯

算法小细节之数组某部分的中间位置的索引

给定一个数组的某个部分,这部分起始索引为L,结束索引为R,求这部分中间位置的索引。

932
来自专栏我的博客

sizeof用法

sizeof()功能:计算数据空间的字节数 1.与strlen()比较 strlen()计算字符数组的字符数,以”\0″为结束判断,不计算为’\...

2884
来自专栏小詹同学

Leetcode打卡 | No.19 删除链表的倒数第N个节点

之前我们说过 C 和 C++ 中的指针是个好东西 ,在解决这类问题很是方便 。然而 python 是没有这个概念的 ,包括链表也是模拟链表的相关操作 。刷题到这...

1442
来自专栏python学习之旅

Python笔记(十七):生成器

Python生成器是创建迭代器的简单方法。简单来说,生成器是一个函数,它返回一个我们可以迭代的对象(迭代器)(一次一个值)。

781
来自专栏书山有路勤为径

1.C与C++

使用c++中的标准库类型vector可以很轻松的完成任务。 不需要管理内存分配,对不同的类型都可以处理

1314
来自专栏烂笔头

Python标准库笔记(10) — itertools模块

3236
来自专栏码云1024

NumPy Ndarray对象

NumPy 中定义的最重要的对象是称为 ndarray 的 N 维数组类型。 它描述相同类型的元素集合。 可以使用基于零的索引访问集合中的项目。

3727
来自专栏深度学习与计算机视觉

算法-删除字符串中的公共字符

题目: 输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。例如,输入“They are students.”和”aeiou”,则删除之后的第一个字...

2276
来自专栏王磊的博客

把字符串转化为类型

问题:可以得到类型的String格式的名称,想要转化为相应的类型? ps:今天定义了好多个枚举类型,把枚举名称存放在一个ComboBox类名,控件值改变的时候要...

2645
来自专栏数据小魔方

左手用R右手Python系列之——迭代器与迭代对象

接触过Python的小伙伴儿肯定都知道,Python中关于迭代器和可迭代对象运用的很广泛。迭代器可以以一种非常友好的方式使用在循环中,不仅节省内存,还能优化代码...

3818

扫码关注云+社区

领取腾讯云代金券