六虎

Swift 数据结构与算法( 30) + S_Leetcode349. 两个数组的交集(集合 (Set),哈希表的应用)

作者：

洋小洋同学

在

Swift 数据结构与算法( ) + Leetcode

概念

运用场景与运用

学习的概念:

  1. 调集 (Set)：调集是一个不包括重复元素的容器。调集的主要长处是查找、刺进和删去的平均时刻复杂度都是 (O(1))。
  2. 哈希表的运用：在这题中，咱们运用了 Swift 的 Set，它底层是基于哈希表完成的。哈希表是经过哈希函数将元素映射到一个固定大小的数组中，然后完成快速的查找、刺进和删去。

实际场景与运用:

  1. 数据库查找：当咱们要查找数据库中的特定数据时，能够运用哈希表或调集来存储这些数据，然后完成快速查找。

    • 技能点：运用哈希表或调集结构存储数据，依据特定的键值进行查找。
  2. 去重：在处理很多数据时，常常需求删去重复的数据。运用调集能够轻松完成这一点。

    • 技能点：将数据刺进到调集中，自动去除重复数据。

iOS App 开发实际运用场景:

  1. 查找联系人：在通讯录运用中，用户或许期望快速查找特定的联系人。经过将联系人的姓名或电话号码存储在哈希表或调集中，能够完成快速查找。

    • 技能点：运用哈希表或调集结构存储联系人信息，供给快速查找功用。
  2. 图片去重：在图片运用或相册运用中，用户或许会多次导入或保存相同的图片。经过运用调集存储每张图片的哈希值，能够轻松检测并删去重复的图片。

    • 技能点：为每张图片生成一个仅有的哈希值，并将这些哈希值存储在调集中。当新图片加入时，比较其哈希值来检测重复。

过错与反思

  1. 特殊情况处理：

    if nums1.count == 0 || nums2.count == 0 {
    return []
}

    这个部分是正确的，当其中一个数组为空时，交集当然也是空的。

  2. 构建字典：

    for item in nums1 {
    //数组不会重复的...
    dict[item] = 1
}

    这儿你假定了 nums1 中的数字都是不重复的，然后将每个数字放入字典中并设置其值为1。但标题并没有明确指出 nums1 中的数字是仅有的，所以这个假定或许是过错的。

  3. 处理 nums2：

    for item2 in nums2 {
    if let newNumber = dict[item2] {
        var newN = newNumber + 1
        dict[item2] = newN
    } else {
        dict[item2] = 1
    }
}

    这儿你企图增加 nums2 中每个数字在字典中的计数。但问题是，当你在 nums1 中没有找到某个数字但在 nums2 中找到时，你仍然在字典中为该数字设置了值。这意味着你的字典现在包括了 nums1 和 nums2 中的一切数字，而不只仅是 nums1 中的数字。

  4. 构建成果数组：

    for item in dict.keys {
    let newNumber:Int = dict[item] ?? 0
    if newNumber > 1 {
        nums3.append(item)
    }
}

    在这儿，在成果数组中添加了字典中计数大于1的一切数字。但考虑到上面的问题，这或许会导致一些不在 nums1 中的数字被过错地添加到成果数组中。

为什么会犯这个过错？

或许的原因是，你或许假定了 nums1 中的数字是仅有的，并且你企图运用单个字典来盯梢两个数组中的数字，而没有正确地区分哪些数字是只在 nums1 中呈现的，哪些数字是在两个数组中都呈现的。

如何防止？

  1. 在编写代码之前，保证你完全理解了标题的要求。
  2. 当你以为已经解决了问题时，运用几个示例来测验你的解决方案，特别是那些或许损坏你的假定的示例。
  3. 考虑运用两个字典或调集，一个用于 nums1，另一个用于交集。

这个解决方案不只更简练，并且能够保证正确地找到两个数组的交集。

标题

349.两个数组的交集

给定两个数组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, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000
class Solution {
    func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
    }
}

解题思路‍ ♀️

鸿沟思考

代码

第一遍过错思路

class Solution {
    func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        var nums3:[Int] = []
        var dict:[Int:Int] = [:]
        for item in nums1 {
            //数组不会重复的...
            dict[item] = 1
        }
        for item2 in nums2 {
            if let newNumber = dict[item2] , newNumber >= 1 {
//                var newN = newNumber + 1
//                dict[newNumber] = newN
                nums3.append(item2)
            } else {
                dict[item2] = 1
            }
        }
        return nums3
    }
}

//数组不会重复的…
呵呵…
人家便是重复了. 艹

正确答案

**class** Solution {
  **func** intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
   
    **if** nums1.count == 0 || nums2.count == 0 {
     **return** []
    }
   
    **var** nums3:[Int] = []
    **var** dict:[Int:Int] = [:]
    **for** item **in** nums1 {
      //数组不会重复的...
      dict[item] = 1
    }
   
    **for** item2 **in** nums2 {
     
      **if** **let** newNumber = dict[item2] {
        **var** newN = newNumber + 1
        dict[item2] = newN
      }
    }
   
    **for** item **in** dict.keys {
      **let** newNumber:Int = dict[item] ?? 0
      **if** newNumber > 1 {
        nums3.append(item)
      }
    }
    **return** nums3
  }
}

优化答案

class Solution {
    func intersection(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        let set1 = Set(nums1)
        var resultSet = Set<Int>()
        for num in nums2 {
            if set1.contains(num) {
                resultSet.insert(num)
            }
        }
        return Array(resultSet)
    }
}

时空复杂度分析

的时刻复杂度为 O(m+n)。

更多文章