数组中重复的数字

问题描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3。
分析
思路1
根据元素的范围为0 - (n - 1)这个限制可以使用哈希的思想。初始化一个大小为n的数组A，数组全部赋值为-1，之后依次遍历目标数组B，判断A[B[i]]是否等于-1如果等于就将A[B[i]]赋值为i，如果不等于-1就说明找到相同的值了，并且返回A[B[i]]。
这是一个时间和空间都是O(n)的算法。
思路2
这个思路是在哈希的基础上进行思考的，它把值的搜索和调整哈希放在了一起进行。具体实现依次遍历每个元素，之后判断是否和依次遍历的顺序值i相同，如果不相同就进行调整，使之有序（也就是哈希调整），是先进行判断，如果number[i] == number[number[i]]，这一点其实和上面的A[B[i]]是有相似之处。如果不相等就去调整，如果相等就返回相等的值。
Python实现

# coding:utf-8
# 查找数组中重复的数字
# 时间O(n), 空间O(1)
def duplicate(number):
	#列表为空
	if(len(number) == 0):
		return False
	
	#列表范围在0 - (n - 1)
	if(not(min(number) >= 0 and max(number) <= (len(number) - 1))):
		return False
	
	#calc
	i = 0
	while(i < len(number)):
		while(number[i] != i):
			if(number[i] == number[number[i]]):
				return number[i]
			tmp = number[i]
			number[i] = number[tmp]
			number[tmp] = tmp
		i += 1;
	#没有相同元素	
	return False

def test():
	#一个重复的最小值:1
	t1 = [2, 1, 3, 1, 4]	
	print duplicate(t1)
	#一个重复的最大值:4
	t1 = [2, 4, 3, 1, 4]	
	print duplicate(t1)
	#两个重复的值：2
	t1 = [2, 4, 2, 1, 4]	
	print duplicate(t1)
	#没有重复的值:False
	t1 = [2, 1, 3, 0, 4]	
	print duplicate(t1)
	#没有重复的值但超越取值范围:False
	t1 = [2, 1, 3, 4, 5]	
	print duplicate(t1)
	#空:False
	t1 = []	
	print duplicate(t1)

test()