50. 数组中重复的数字

题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

思路
思路一：
开辟一个新的数组空间，将遍历过的数插入新的数组中，如果遇到重复的，就返回True。增加了额外的空间，时间复杂度为O(N)，空间复杂度为O(N)。

思路二：
利用长度为n的数组里的所有数字都在0到n-1的范围内这一个条件，数组中的每一个数字值小于数组长度，如果数组中无任何重复的数字，则数组从小到大排序后理应满足第i个位置对应的元素值是i。
遍历数组，判断当前位的值和下标是否相等：
若相等，则遍历下一位；
若不等，则将当前位置i上的元素和a[i]位置上的元素比较：若它们相等，则找到了第一个相同的元素，程序结束可以返回；若不等，则将它们两交换。换完之后a[i]位置上的值和它的下标a[i]是对应的，但i位置上的元素和下标并不一定对应；重复判断位置i上的元素和a[i]位置上的元素比较的操作，直到当前位置i的值也为i，将i向后移一位，再重复位置i上的元素和a[i]位置上的元素的比较，直到遍历完成或者找到重复数字。
时间复杂度为O(n)，空间复杂度为O(1)
举例说明：{2,3,1,0,2,5,3}
0(索引值)和2(索引值位置的元素)不相等，并且2(索引值位置的元素)和1(以该索引值位置的元素2为索引值的位置的元素)不相等，则交换位置，数组变为：{1,3,2,0,2,5,3}；
0(索引值)和1(索引值位置的元素)仍然不相等，并且1(索引值位置的元素)和3(以该索引值位置的元素1为索引值的位置的元素)不相等，则交换位置，数组变为：{3,1,2,0,2,5,3}；
0(索引值)和3(索引值位置的元素)仍然不相等，并且3(索引值位置的元素)和0(以该索引值位置的元素3为索引值的位置的元素)不相等，则交换位置，数组变为：{0,1,2,3,2,5,3}；
0(索引值)和0(索引值位置的元素)相等，遍历下一个元素；
1(索引值)和1(索引值位置的元素)相等，遍历下一个元素；
2(索引值)和2(索引值位置的元素)相等，遍历下一个元素；
3(索引值)和3(索引值位置的元素)相等，遍历下一个元素；
4(索引值)和2(索引值位置的元素)不相等，但是2(索引值位置的元素)和2(以该索引值位置的元素2为索引值的位置的元素)相等，则找到了第一个重复的元素。

代码实现
思路一：开辟新的空间

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        nums = []
        for i in numbers:
            if i not in nums:
                nums.append(i)
            else:
                duplication[0] = i
                return True
        return False

思路二：不开辟新的空间

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        length = len(numbers)
        if length == 0:
            return False
        index = 0
        while(index < length):
            if(numbers[index] == index):
                index += 1
            else:
                index_num = numbers[index]
                if(index_num == numbers[index_num]):
                    duplication[0] = index_num
                    return True
                else:
                    temp = numbers[index]
                    numbers[index] = numbers[index_num]
                    numbers[index_num] = temp
        return False