面试题3：数组中重复的数字

题目一：找出数组中任意一个重复的数字

解法1

直接将数组排序，从头开始扫描数组是否重复，排序一个数组的时间复杂度为O(nlogn),本段代码使用python内置函数sort，底层是归并排序，排序之后的数组依次进行判断即可。

class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        if numbers is None or len(numbers)<=0:   #根据测试用例添加条件
            return False
        numbers.sort()
        if numbers[0]<0 or numbers[len(numbers)-1]>len(numbers)-1:
            return False
        for i in xrange(len(numbers)-1):
            if numbers[i]==numbers[i+1]:
                duplication[0]= numbers[i]
                return True
        return False

解法2

利用字典求解，时间复杂度为O(n)，但是需要额外的O(n)空间复杂度来构建字典。思想为将出现的字符作为字典的key，遍历字典，如果key已经存在则返回字符，否则将该键值添加到字典中。

class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        if numbers is None or len(numbers)<=0:
            return False
        dic = {}
        for i in numbers:
            if i<0 or i > len(numbers)-1:
                return False
            elif i in dic:
                duplication[0] = i
                return True
            else:
                dic[i]=0
        return False

解法三

进阶方法-时间复杂度为O(n)，空间复杂度为O(1)。
重排数组：从头到尾扫描数组的每个数字，当扫描到下标为i的数字时，首先比较这个数字（假设为m）是否等于i,如果是，接着扫描下一个数字；如果不是，那么再将它和下标为m的数字对比，如果两者不相等，就把它和第m个数字交换，把m放到属于它的位置，如果两者相等，那么就找到了一个重复的数字。重复这个过程，知道发现一个重复的数字。

解题代码：(根据代码分析复杂度：所有操作都在输入数组上进行，不需要额外分配空间，因此空间复杂度为O(1);尽管代码中有一个两重循环，但是每个数字最多只要交换两次就能找到它自己的位置，因为总的时间复杂度为O(n))

class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        if numbers==None or len(numbers)<=1:
            return False
        for i in range(len(numbers)):
            if numbers[i]<0 or numbers[i]>len(numbers)-1:
                return False
            else:
                while (i!=numbers[i]):
                    if numbers[i] == numbers[numbers[i]]:
                        duplication[0]= numbers[i]
                        return True
                    else:
                        temp=numbers[i]
                        numbers[i]=numbers[temp]
                        numbers[temp]=temp
                        
        return False

题目二 ：拓展：不修改数组找出重复的数字。

在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组，例如输入长度为8的数组[2,3,5,4,3,2,6,7]，那么对应的输出是重复的数字为2或3。

解法1 题目一的字典法即可，时间复杂度O(n),空间复杂度也为O(n)

解法2 利用二分查找l类似的思路，依次分路查找重复数字的范围，时间复杂度为O(nlogn)，但是空间复杂度为O(1)。这种解法相比1是用时间消耗换取少的空间利用。

注意：解法2不能找出所有的重复数字，这个方法不能分辨在【1,2】范围内是有两个同一数字或者每个数字含有一个。

class Solution:
    def duplicate(self, numbers):
        # write code here
        if len(numbers)<=1 or numbers is None:
            return -1
        start = 1
        end = len(numbers)-1
        while start <= end:
            mid = int((end + start)/2)
            count = self.countRange(numbers,start,mid) #类里面调用函数要用self.xx
            if start == end:
                if count > 1:
                    return start
                else:
                    break
            if count > mid - start + 1:
                end = mid
            else:
                start = mid+1
        return -1

    def countRange(self,numbers,start,end):
    #计算数组中的元素大于等于start，小于等于end的元素的个数
        length = len(numbers)
        count =0
        for i in range(length):
            if numbers[i] <= end and numbers[i] >=start:
                count += 1
        return count

if __name__=="__main__":
    print(Solution().duplicate([2,3,5,4,3,2,6,7]))
#out: 3