题目一：找出数组中重复的数字。
在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例1：
输入长度为7的数组
[2, 3, 1, 0, 2, 5, 3]
那么对应的输出是重复的数字2或者3，数组内的数字大小都在0~6之间（包含）。
示例2：
输入长度为6的数组
[1, 2, 1, 4, 3, 5]
那么对应的输出是重复的数字1或者3
思路：
- 1、排序数组，然后对比前后数据是否一致。时间复杂度O(nlogn)，空间复杂度最好的情况O(1)；
- 2、遍历数组，将出现的数字保存到一个字典中，如果遍历到的数字存在于字典内，说明出现了重复的数字。时间复杂度O(n)，空间复杂度最差O(n)；
- 3、书中的解法：对数组进行排序，因为数据大小是
0~n-1的，那么数组内的数字就可以和数组的下标对应起来，先将数组内数据进行交换排序，将数据放到对应的下标位置：
[2, 3, 1, 0, 2, 5, 3]
[1, 3, 2, 0, 2, 5, 3]
[3, 1, 2, 0, 2, 5, 3]
[0, 1, 2, 3, 2, 5, 3]
当遍历到第4个数2时，会跟2的下标进行交换，然后发现下标为2的位置已经有相同的数据，说明有重复。
代码如下：
func duplicate(_ nums: inout [Int]) -> (Bool, Int) {
if nums.isEmpty {
return (false, -1)
}
if nums.count == 1 {
return (false, -1)
}
var index = 0
var cur = 0
var temp = 0
while index < nums.count {
cur = nums[index]
if cur != index {
temp = nums[cur]
/*
如果交换的数所在的下标在排序好的下标之前，说明有重复
如果交换的数和需要交换的数相同，说明有重复
*/
if temp < index || temp == nums[temp] {
return (true, temp)
} else {
// 交换2个数据
nums[index] = temp
nums[cur] = cur
}
}else {
index += 1
}
}
return (false, -1)
}
该解法时间复杂度O(n)，空间复杂度O(1)。
题目二：不修改数组找出重复的数字
在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。
例如,如果输入长度为
8的数组
[2,3,5,4,3,2,6,7]
输出是重复的数字2或者3。
思路：
解法利用了二分查找的思想，扫描区间内数字的数量进行对比得到的重复数字。原理就是，如果不存在重复的情况下，区间内的数字总是数量count是小于等于区间mid - l + 1大小的，比如1~4之间的数的数量不重复的情况下最大就是1-4这4个数，那么如果超过4个数，肯定存在重复：
func getDuplication(_ nums: [Int]) -> Int {
guard nums.count > 1 else {
return -1
}
var l = 1, r = nums.count - 1, mid = 0
while l <= r {
mid = l + (r - l) >> 1
// 计算l~mid中间的数有多少个
var count = 0
for i in 0..<nums.count {
if nums[i] >= l && nums[i] <= mid {
count += 1
}
}
// 搜索完所有区间
if l == r {
if count > 1 { // 定位到重复的数字
return l
} else {
break
}
}
// 如果中间数字的数量大于正常数量，说明有重复，r左移，从左边继续搜索
if count > (mid - l + 1) {
r = mid
}else { // 从右边搜索，l右移
l = mid + 1
}
}
return -1
}
时间复杂度O(nlogn)，空间复杂度O(1)。
另外附上二分查找代码：
/*
标准二分查找：输入有序数组和查找的数，返回所在的index，如果不存在返回-1
*/
func binarySearch(_ nums: [Int], target: Int) -> Int {
if nums.count == 0 {
return -1
}
if nums.count == 1 {
if nums[1] == target { return 0 }
}
var l = 0
var r = nums.count - 1
var mid = 0
while l <= r {
mid = l + (r - l) / 2
if nums[mid] == target {
return mid
} else if (nums[mid] > target) {
r = mid - 1
} else {
l = mid + 1
}
}
return -1
}
PS：因为语言与官方不同，写法略有区别，单元测试量不够，如有错误，请留言指出。
网友评论