Swift 两个数组的交集 II - LeetCode

韦弦zhy

发布于 2018-09-11 12:48:00

1.3K0

发布于 2018-09-11 12:48:00

文章被收录于专栏：韦弦的偶尔分享

两个数组的交集 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中开始做初级算法这一章节，将做的题目在此做个笔记吧。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018.03.31 ，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度