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)。

这篇好文章是转载于：学新通技术网