题目：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
暴力算法
在数组中查找重复的数字，首先想到的是遍历，直接使用两次 for 循环每次取出未比较过的一个数字和接下里的每个数字比对找出重复的数字，代码：
func findRepeatNumber1(_ nums: [Int]) -> Int {
if nums.count < 2 {
return -1
}
for i in 0..<nums.count {
for j in (i+1)..<nums.count {
if nums[i] == nums[j] {
return nums[i]
}
}
}
return -1
}
以上算法实现的复杂度分析：
- 时间复杂度是 O(n^2)
- 空间复杂度是 O(1)
该算法是最先能想到的，简单粗暴。但是没啥实际应用，太过耗时了在 LeetCode上，2 <= n <= 100000的测试用例都因太过耗时没有通过。
排序后查找
根据之前暴力算法，我们考虑可以将数组排序后再遍历一次就能够找到重复数字，代码如下：
func findRepeatNumber2(_ nums: [Int]) -> Int {
if nums.count < 2 {
return -1
}
let orderedNums = nums.sorted()
var prevNum = orderedNums.first!
for i in 1..<orderedNums.count {
if prevNum == orderedNums[i] {
return prevNum
}else {
prevNum = orderedNums[i]
}
}
return -1
}
以上算法实现的复杂度分析：
- 时间复杂度是 O(nlogn)
- 空间复杂度是 O(n)
算法中使用到 O(n)的大小空间存放排序好的数组，然后再次遍历一次查找结果总的时间复杂度：O(nlogn) + O(n)。
引入Set集合
我们可以引入一个set来存放没有重复的数字，每次添加新的数字前，判断set中是否包含该数字。
func findRepeatNumber3(_ nums: [Int]) -> Int {
if nums.count < 2 {
return -1
}
var set = Set<Int>()
for num in nums {
if set.contains(num) {
return num
}else {
set.insert(num)
}
}
return -1
}
以上算法实现的复杂度分析：
- 时间复杂度是 O(n)
- 空间复杂度是 O(n)
借助一个 n 大小的 Set，我们可以通过一次遍历就能够找到数组中重复的数字，典型的以空间换时间的算法。
书中原解
题目中提到了数组中的数字都在 0~n-1 的范围。如果数组中没有重复的数字，那么排序后的数组每个数和对应的下标应该是相等的。如果有重复的数字，那么有些位置可能会存在多个数字，有些位置可能没有数字。
直接上代码
func findRepeatNumber4(_ nums: inout [Int]) -> Int {
if nums.count < 2 {
return -1
}
var nums = nums
for i in 0..<nums.count {
let m = nums[i]
while i != m {
if m == nums[m] {
return m
}
nums.swapAt(i, m)
}
}
return -1
}
以上算法实现的复杂度分析：
- 时间复杂度是 O(n)
- 空间复杂度是 O(n)(Swift中传递的参数无法修改，除非是用inout修饰，不然还是需要O(n)空间来存放，其它编程语言可以实现O(1)的空间复杂度)
我们在一次遍历的时候重排数组，且比较数字对应的下标是否相同。当我们扫描到下标为i的值为 m 的时候，首先比较 i 和 m 是否相同，如果相同，扫描下一个数字。不同则将数组下标为 m 的数字 和 m 比较。此时如果两个数字相同。则找到重复数字返回结果。不同则交换两个数据。重复这个过程。
网友评论