【Swift 算法实战】判断数组中是否存在重复元素

  大家好，我是 展菲，目前在上市企业从事人工智能项目研发管理工作，平时热衷于分享各种编程领域的软硬技能知识以及前沿技术，包括iOS、前端、Harmony OS、Java、Python等方向。在移动端开发、鸿蒙开发、物联网、嵌入式、云原生、开源等领域有深厚造诣。

图书作者：《ESP32-C3 物联网工程开发实战》
图书作者：《SwiftUI 入门，进阶与实战》
超级个体：COC上海社区主理人
特约讲师：大学讲师，谷歌亚马逊分享嘉宾
科技博主：极星会首批签约作者

摘要

在这篇文章中，我们将实现一个简单的算法来判断一个整数数组中是否包含至少一个重复元素。根据题目要求，如果数组中任意元素出现至少两次，返回 true，否则返回 false。我们将介绍几种常见的解法，并重点关注效率和性能优化。

描述

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入： nums = [1,2,3,1]

输出： true

解释：

元素 1 在下标 0 和 3 出现。

示例 2：

输入： nums = [1,2,3,4]

输出： false

解释：

所有元素都不同。

示例 3：

输入： nums = [1,1,1,3,3,4,3,2,4,2]

输出： true

提示：

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
  

题解答案

为了判断数组中是否存在重复元素，我们可以使用以下几种方法：

1. 使用 Set（集合）来判断
   由于集合中的元素是唯一的，我们可以利用这一点来快速判断是否有重复的元素。如果在插入元素时发现该元素已经存在于集合中，则表示有重复元素。

2. 使用暴力法
   通过嵌套循环遍历每对元素，逐一比较，判断是否有重复值。尽管实现简单，但性能较差，尤其是在大数组时效率低下。

3. 排序法
   将数组排序后，只需遍历一次数组，检查相邻元素是否相等。排序的时间复杂度为 O(n log n)，在一定情况下可能比 Set 更高效。

在这里，我们重点介绍第一种方法，使用 Swift 中的 Set 来判断是否有重复元素。

题解代码分析

思路

• 遍历数组，尝试将每个元素加入 Set 中。
• 如果元素已经存在于 Set 中，返回 true，表示存在重复元素。
• 如果遍历完成后没有发现重复元素，返回 false。

Swift 代码实现

func containsDuplicate(_ nums: [Int]) -> Bool {
    var seen = Set<Int>()

    for num in nums {
        if seen.contains(num) {
            return true // 找到重复元素
        }
        seen.insert(num) // 将当前元素插入 Set
    }

    return false // 没有重复元素
}

示例测试及结果

示例 1：

let nums1 = [1, 2, 3, 1]
print(containsDuplicate(nums1)) // 输出 true

示例 2：

let nums2 = [1, 2, 3, 4]
print(containsDuplicate(nums2)) // 输出 false

示例 3：

let nums3 = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
print(containsDuplicate(nums3)) // 输出 true

时间复杂度与空间复杂度

• 时间复杂度：O(n)
  遍历数组一次，每次操作 Set 的插入和查找都是常数时间复杂度 O(1)。

• 空间复杂度：O(n)
  最坏情况下，Set 会存储 n 个元素，因此空间复杂度是 O(n)。

总结

本文介绍了如何高效判断数组中是否有重复元素。我们使用了 Set 数据结构，利用其元素唯一的特性，可以在 O(n) 的时间复杂度内完成判断。相比暴力法和排序法，使用 Set 提供了一种简洁且高效的解决方案。

这种方法不仅适用于整数数组，还能处理其他类型的数据，具有广泛的应用场景。

未来如果有更复杂的需求（如需要额外的信息，或者需要考虑其他数据结构的优化），可以考虑使用哈希表或其他数据结构，进一步提升算法的性能和可扩展性。

参考资料

• Swift 官方文档
• LeetCode 题目解答：Contains Duplicate