题目一：找出数组中重复的数字。 在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中人一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3。
题目二：不修改数组找出重复的数字。 在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或者3。
题目一中标红的字眼是关键。因为在正常情况下，要找出一个数组中的重复元素并不需要直到这些元素的范围，但是这道题给了这么个限制条件，要么是误导我们的，要么就是解题的关键了。
通过dict记录该数组中每一个的元素出现的次数，当再次出现时次数加1，这时返回这个元素即可。 当然也可以用一个list来记录该数组的元素。遇到元素m将之放到list中下标为m的位置，若放置的时候，该位置已经有值了，则表明该元素重复了。 时间复杂度是O(n)，空间复杂度是S(n)。
思路1中并没有将条件在一个长度为n的数组里的所有数字都在0~n-1的范围内利用起来。要想得到效率更高的算法，这个条件是关键。
如果将数组排序且数组中没有重复的数字，那么数组中的元素和下标是完全相等的。也就是说，数字0的下标就是0， 1的下标就是1， n-1的下标就是n-1。但是，题目中数组并不一定是排序好的，要将数组排序，那么时间复杂度是O(nlogn)(快排的时间复杂度)，所以需要在不对数组进行排序的情况下利用到这个关键条件。
假设当前元素是m，下标是i，若m≠i，那么就交换元素m和下标为m，这样元素m和下标m就对应上了。如果交换的时候发现元素m对应的位置（下标m）出已经有了一个m元素，那么元素m就重复了。 时间复杂度是O(n)，空间复杂度是S(1)。
既然使用额外的容器会增加空间复杂度，那么能不能使用该数组自身来标记哪些元素已经出现，哪些元素没有出现呢？答案是可以。
因为数组中所有的数字都在0~n-1这个范围内。若当前下标为i，元素为数字m，那么将下标为m的元素的值加上n，这样只要通过判断下标m的元素是否 >=n 就能够知道是否已经出现过数字m了。 时间复杂度是O(n)，空间复杂度是S(1)。
思路4是针对题目二的。题目二在题目一的基础上增加了一个限制条件:不能修改原数组。 那么应该如何去做呢?
关键：如果1~n的数字没有重复，那么1~n的这个范围内只会有n个数字，但是因为有数字重复了，1~n这个范围内数字个数为n+1。
Step 1：1~n的数字从中间的数字m分为两部分，前面一半为1~m，后一半为m+1~n。如果1~m的数字的数目超过m，那么这一半的区间中一定包含重复的数字；否则，另一半m+1~n的区间里一定包含重复的数字； Step 2：将包含重复数字的那一半区间再从中间数字分为两个部分，重复Step 1的工作，直到找到一个重复的数字。 有些类似于二分查找算法。 时间复杂度O(nlogn)，空间复杂度S(1)。
思路1的代码实现：
def find_duplicate_number(array):: """从数组中找出一个重复的元素 :param array: 数组。 :return """ # 边界条件 if not isinstance(array, list): raise TypeError('输入类型并不是list！') for element in array: if element < 0 or element > len(array)-1: raise ValueError('列表中的元素应该在0~n-1范围内！') for element in array: element_count = element_count.get(element, 0) + 1 if element_count.get(element, 0) > 1: return element return -1思路2的代码实现：
class Solution: def find_duplicate_number(self, array): """从数组中找出一个重复的元素 :param array: 数组。 :return """ # 边界条件 if not isinstance(array, list): raise TypeError('输入类型并不是list！') for element in array: if element < 0 or element > len(array)-1: raise ValueError('列表中的元素应该在0~n-1范围内！') for index in range(len(array)): while index != array[index]: if array[index] != array[array[index]]: # 不能使用这种方式去交换两者的值，想想为什么？因为先修改了array[index]，那么对应的array[array[index]]也变了。 # array[index], array[array[index]] = array[array[index]], array[index] temp = array[index] array[index] = array[array[index]] array[array[index]] = temp else: return array[index] return -1思路3的实现：
class Solution: def find_duplicate_number(self, array): """从数组中找出一个重复的元素 :param array: 数组。 :return """ # 边界条件 if not isinstance(array, list): raise TypeError('输入类型并不是list！') for element in array: if element < 0 or element > len(array)-1: raise ValueError('列表中的元素应该在0~n-1范围内！') for index in range(len(array)): if array[index] >= n: # 表明数字index重复了 return index else: array[array[index]] += len(array) return -1思路4的实现：
class Solution: def find_duplicate_number(self, array): """从数组中找出一个重复的元素 :param array: 数组 :return """ if not isinstance(array, list): raise TypeError('输入的类型并不是list!') for element in array: if element < 1 or element >= n: raise ValueError('列表中的元素应当在0~n-1范围内!') start = 0 end = len(array) - 1 while start <= end: middle = (start + end) // 2 count = self.count_range(array, start, middle) if start == end: if count > 1: return start else: break if count > (middle - left + 1): right = middle else: left = middle + 1 return -1 def count_range(self, array, start, end): """数组中元素在start~end范围内的数量 :param array: 数组 :param start: 范围下限 :param end: 范围上限 """ if not array: return 0 count = 0 for element in array: if start <= element <= end: count += 1 return count通常我们第一时间想到的算法一般都不是最优的算法，从时间和空间两方面来思考能否进一步优化。
需要注意题目中是否给出了多余的条件（像本题中，如果使用思路1那么，条件中的在一个长度为n的数组里的所有数字都在0~n-1的范围内这个限定条件根本就没有用起来），如果是，那么这个多余的条件可能就是优化的关键所在了。
通过自己来记录哪些数字已经存在了，不适用额外的空间。
多画图，帮助大脑思考。
[1] 剑指offer丛书 [2] 剑指Offer——名企面试官精讲典型编程题
