[Swift]LeetCode442.数组中重复的数据|FindAllDuplicatesinanArray

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10339500.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。

找到所有出现两次的元素。

你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？

示例：

输入:
[4,3,2,7,8,2,3,1]

输出:
[2,3]

136ms

 1 class Solution {
 2     func findDuplicates(_ nums: [Int]) -> [Int] {
 3         var nums = nums
 4         var result = [Int]()
 5         for num in nums {
 6             nums[num - 1] = -nums[num - 1]
 7             if (nums[num - 1] > 0) {
 8                 result.append(num)
 9             }
10         }
11         return result
12     }
13 }

144ms

 1 class Solution {
 2     func findDuplicates(_ nums: [Int]) -> [Int] {
 3         var res = [Int]()
 4         var nums = nums
 5         for i in 0..<nums.count {
 6             let index = abs(nums[i]) - 1
 7             if nums[index] < 0 {
 8                 res.append(abs(index + 1))
 9             }
10             nums[index] = -nums[index]
11         }
12         return res
13     }
14 }

512ms

 1 class Solution {
 2     func findDuplicates(_ nums: [Int]) -> [Int] {
 3         var nums = nums
 4         var res:[Int] = [Int]()
 5         var n:Int = nums.count
 6         for i in 0..<n
 7         {
 8             nums[(nums[i] - 1) % n] += n
 9         }
10         for i in 0..<n
11         {
12             if nums[i] > 2 * n
13             {
14                 res.append(i + 1)
15             }
16         }
17         return res
18     }
19 }

708ms

 1 class Solution {
 2     func findDuplicates(_ nums: [Int]) -> [Int] {
 3         guard nums.count > 1 else {
 4             return []
 5         }
 6         var set = Set<Int>()
 7         var arr = [Int]()
 8         for i in nums {
 9             if set.contains(i) {
10                 arr.append(i)
11             } else {
12                 set.insert(i)
13             }
14         }
15         return arr
16     }
17 }