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

题目描述

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

知识点

数组

Qiang的思路

遍历整个数组，对每个数字进行标记，出现为True，没出现为False，当遍历的时候发现已经为True了就找到了重复的数字，不为True就将其标记为True并继续遍历。

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

时间复杂性分析

该代码首先需要得到一个全为False的flag数组，时间复杂度为O(n)。然后通过遍历的方式去判断是否当前的数为重复出现的数，时间复杂度为O(n)。综上，时间复杂度为O(n)。

空间复杂性分析

该代码需要一个长度为n的flag数组，故空间复杂度为O(n)。

Book中思路

同样采取遍历的方式，在遍历的同时判断当前元素i是否等于当前下标（因为整个数组长为n，元素大小从0到n-1），如果不相等则将i与下标为i的元素进行比较，如果相等则找到了重复的元素，如果不相等则交换。如果当前元素i等于下标则继续遍历。

这种思路可以将元素i放到下标为i的位置，这样就相当于做了标记。

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        i=0
        while i<len(numbers):
            if i==numbers[i]:
                i+=1
                continue
            if numbers[i]==numbers[numbers[i]]:
                duplication[0]=numbers[i]
                return True
            # numbers[i],numbers[numbers[i]]=numbers[numbers[i]],numbers[i]
            # 这种写法是不对的，numbers[numbers[i]]受到了numbers[i]的影响
            a=numbers[i]
            numbers[i]=numbers[a]
            numbers[a]=a
        return False

时间复杂性分析

对于每个元素，最多交换两次就能找到属于自己的位置，所以总的时间复杂度为O(n)。
这个地方我有一些不同意，作者在书中写的是每个元素最多交换两次，但是这两次实际上前一次是因为上一个元素交换导致的，下一次又是下一个元素两次交换中的第一次，所以我认为每个元素实际上最多只需要交换一个就能到达所在的位置。

空间复杂性分析

显然，这套代码的时间复杂度为O(1)。

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。