[Swift]LeetCode287.寻找重复数|FindtheDuplicateNumber

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

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

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

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

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

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

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2

示例 2:

输入: [3,1,3,4,2]
输出: 3

说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

32ms

 1 class Solution {
 2     func findDuplicate(_ nums: [Int]) -> Int {
 3         var l = 1
 4         var r = nums.count - 1
 5         while l < r {
 6             let mid = (l + r) / 2
 7             var count = 0
 8             for i in 0 ..< nums.count {
 9                 if nums[i] <= mid {
10                     count += 1
11                 }
12             }
13             if count <= mid {
14                 l = mid + 1
15             } else {
16                 r = mid
17             }
18         }
19         return l
20     }
21 }

52ms

 1 class Solution {
 2     func findDuplicate(_ nums: [Int]) -> Int {
 3         var sorted = nums.sorted()
 4         var i = 1
 5         while i < sorted.count {
 6             if sorted[i] == sorted[i - 1] {
 7                 return sorted[i]
 8             }
 9             i += 1
10         }
11         return -1
12     }
13 }

80ms

 1 class Solution {
 2     func findDuplicate(_ nums: [Int]) -> Int {
 3         var slow = 0, fast = 0, tmp = 0
 4         while true {
 5             slow = nums[slow]
 6             fast = nums[nums[fast]]
 7             if slow == fast {
 8                 break
 9             }
10         }
11         while true {
12             slow = nums[slow]
13             tmp = nums[tmp]
14             if slow == tmp {
15                 break
16             }
17         }
18         
19         return tmp
20     }
21 }

92ms

 1 class Solution {
 2     func findDuplicate(_ nums: [Int]) -> Int {
 3         var nums = nums
 4         
 5         for index in 0..<nums.count {
 6             
 7             while nums[index] != index {
 8                 if nums[index] == nums[nums[index]] {
 9                     return nums[index]
10                 }
11                 nums.swapAt(index, nums[index])
12             }
13             
14         }
15         
16         return 0
17         
18     }
19 }

96ms

 1 class Solution {
 2     func findDuplicate(_ nums: [Int]) -> Int {
 3         var res = [Int:Int].init()
 4         
 5         for i in 0..<nums.count {
 6             if res.keys.contains(nums[i]) {
 7                 return nums[i]
 8             }else{
 9                 res[nums[i]] = i
10             }
11         }
12         return 0
13     }
14 }

120ms

 1 class Solution {
 2     func findDuplicate(_ nums: [Int]) -> Int {
 3         
 4         var start = 0
 5         var end = nums.count
 6         
 7         while start < end {
 8             let mid = (start + end) / 2
 9             var count = 0
10             
11             nums.forEach{ if $0 <= mid { count += 1 } }
12             
13             if count > mid {
14                 end = mid
15             }else{
16                 start = mid + 1
17             }
18         }
19 
20         return start
21     }
22 }

124ms

 1 class Solution {
 2     func findDuplicate(_ nums: [Int]) -> Int {
 3         var set = Set<Int>()
 4         
 5         for item in nums {
 6             if set.contains(item) {
 7                 return item
 8             }else{
 9                 set.update(with: item)
10             }
11         }
12         
13         return 0
14     }
15 }

132ms

 1 class Solution {
 2     func findDuplicate(_ nums: [Int]) -> Int {
 3         var set = Set<Int>()
 4         for (index, num) in nums.enumerated() {
 5             set.insert(num)
 6             if index == set.count {
 7                 return num
 8             }
 9         }
10         return 0
11     }
12 }