题解 | #数组中重复的数字#

1.问题形式化

输入：n个数组成的无序数组arr，数值为0~n-1；

输出：数组中任意一个重复的数。

2.题目分析

（注：参考鸠摩罗什）

要求时间复杂度为O（n），直接用排序来找重复数字最快也要O（nlogn）。因此，不能直接排序，题目中一个隐含信息是n个数的数值在0~n-1之间，因此可以通过如下方式进行：

遍历数组，从前往后将数组中的每个数放到该数数值对应的位置上，每次放置时只需判断要放置的位置的数值与该数数值是否相等即可，如果相等，直接返回该数即可。

3.伪代码

def multi_numbers(arr,n):
	i=0
    while i<n do:
    	if arr[i]==i then
        	i+=1
        else then:
        	if arr[i]==arr[arr[i]] then
            	return arr[i]
            else then:
            	swap(arr[i],arr[arr[i]])
            end if
        end if
    end while
    return -1
    

4.python代码

    def duplicate(self , numbers: List[int]) -> int:
        # write code here
        n=len(numbers)
        i=0
        while i<n:
            if numbers[i]==i:
                i+=1
            else:
                if numbers[i]==numbers[numbers[i]]:
                    return numbers[i]
                else:
                    numbers[numbers[i]],numbers[i]=numbers[i],numbers[numbers[i]]
        return -1