剑指offer：数组中重复的数字-创新互联
题目描述：
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
# -*- coding: utf-8 -*-
# @Time : 2019-04-15 17:31
# @Author : Jayce Wong
# @ProjectName : job
# @FileName : duplicate_num_in_array.py
# @Blog : https://blog.51cto.com/jayce1111
# @Github : https://github.com/SysuJayce
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# 完整的做法是先进行输入合法性检查，然后将每个数字放到它应该在的下标，在每次交换之前先检查该下标是否已保存了正确的数字，
# 如果是则该数字是一个重复数字
# 时间复杂度O(n)，空间复杂度O(1)。由于每个数字最多交换两次就可以放到正确的位置(第一次被从不正确的位置换到另一个不正确的位置，
# 然后第二次就会专门为它找到属于它的位置，因此最多是两次)，也就是最多比较2n次，即时间复杂度是O(n)
if not numbers:
return False
if max(numbers) >= len(numbers) or min(numbers) < 0:
return False
for i in range(len(numbers)):
while numbers[i] != i:
if numbers[numbers[i]] == numbers[i]:
duplication[0] = numbers[i]
return True
else:
# 注意这样交换会出现问题，需要先保存一个中间结果，不能直接交换，
# 否则当处理numbers[numbers[i]]的时候会找不到正确的下标
# numbers[i], numbers[numbers[i]] = numbers[numbers[i]], numbers[i]
temp = numbers[i]
numbers[i] = numbers[numbers[i]]
numbers[temp] = temp
return False
def duplicate2(self, numbers, duplication):
# duplicate1()需要对输入数组进行修改，假如要求不修改输入数组，那么可以借鉴二分查找的
# 思想，逐步缩小重复数字所在的区间。
# 但是这种方法不能确保找到所有重复的数字，
# 如果counter(left, right) == right - left + 1，不能排除[left, right]有重复
# 数字的情况，例如[2, 3, 5, 4, 3, 2, 6, 7]中，counter(1, 2) == 2，但是2其实是
# 重复数字
# 由于是借鉴了二分查找的思想，因此while需要循环logn次，counter需要n次运算
# 故时间复杂度O(nlogn), 空间复杂度O(1)
def counter(start, end): # 统计numbers中处于[start, end]之间的数字个数
count = 0
for num in numbers:
if start <= num <= end:
count += 1
return count
if not numbers: # 输入合法性判断
return False
left, right = 0, len(numbers) - 1 # 初始区间为[0, n-1]
while left <= right:
mid = (left + right) >> 1
cnt = counter(left, mid)
# 需要注意这里的循环出口，如果不在循环内判断left==right的情况的话就需要在循环外面
# 再判断一次counter(left, left) == 1
if left == right:
if cnt > 1:
duplication[0] = left
return True
break
if cnt > mid - left + 1:
# 由于是判断了 [left, mid]是否存在重复，并不能排除mid就是重复的数字，
# 因此right不能更新为mid - 1
right = mid
else:
left = mid + 1
return False
def duplicate3(self, numbers, duplication):
# 由于数组中的数字范围已定，可以通过申请一个容量为数字范围的数组然后建立哈希表进行去重
# 时间复杂度O(n), 空间复杂度O(n)
arr = [-1] * len(numbers)
for num in numbers:
if arr[num] == -1:
arr[num] = num
else:
duplication[0] = num
return True
return False另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
当前名称：剑指offer：数组中重复的数字-创新互联
链接URL：http://scyanting.com/article/ghoch.html
