051. 数组中重复的数字

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

Solutions

　　思路一：先将输入数组排序，然后遍历比较当前值和下一个值是否相等：

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        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
            
        numbers.sort()
        for i in range(len(numbers)-1):
            if numbers[i]==numbers[i+1]:
                duplication[0]=numbers[i]
                return True
        return False
# 运行时间：49ms
# 占用内存：6424k

　　思路二：利用哈希表来存数据：

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        if numbers==None or len(numbers)<=1:
            return False
        
        usedDic=set() #集合
        for i in range(len(numbers)):
            if numbers[i]<0 or numbers[i]>len(numbers)-1:
                return False
            if numbers[i] not in usedDic:
                usedDic.add(numbers[i])
            else:
                duplication[0]=numbers[i]
                return True
        return False
# 运行时间：29ms
# 占用内存：5712k

　　思路三：重拍数组。从头到尾扫描数组的每个数字，当扫描到下标为i的数字时，首先比较这个数字（假设为m）是否等于i,如果是，接着扫描下一个数字；如果不是，那么再将它和下标为m的数字对比，如果两者不相等，就把它和第m个数字交换，把m放到属于它的位置，如果两者相等，那么就找到了一个重复的数字。重复这个过程，知道发现一个重复的数字。

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

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        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
        
        for i in range(len(numbers)):
            while (numbers[i]!=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
# 运行时间：26ms
# 占用内存：5752k

Solutions

References