本文共 1551 字，大约阅读时间需要 5 分钟。

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

解法一：

新建一个空列表，遍历输入列表中的元素，如果这个元素不在新列表中，就把他加进去，如果在新列表中，就输出该元素。

class Solution:    def duplicate(self , numbers ):        # write code here        l = []        if len(numbers) == 0:            return -1        for i in numbers:            if i < 0 or i > len(numbers)-1:                return -1            if i not in l:                l.append(i)            else:                return i

解法二：

替换法，解法一中新建了一个列表，消耗了内存。

数组存放原则：numbers[i] = i

遍历数组所有元素，交换不符合数组存放原则的元素：

例如[2,3,1,0,2]

  遍历0位元素2：（交换0位元素2和2位元素1）->[1,3,2,0,2]

  遍历0位元素1：（交换0位元素1和1位元素3）->[3,1,2,0,2]

  遍历0位元素3：（交换0位元素3和3位元素0）->[0,1,2,3,2]

  依次遍历0、1、2、3位置元素，都符合存放原则numbers[i] = i，不做任何操作

  遍历末位元素2，此时末位元素2和2位元素2相等，出现了两次，即数字2位重复元素

class Solution:    def duplicate(self , numbers ):        # write code here        if not numbers:            return -1        i = 0        while i < len(numbers):            if numbers[i] != i:                if numbers[i] == numbers[numbers[i]]:                    return numbers[i]                temp = numbers[numbers[i]]                numbers[numbers[i]] = numbers[i]                numbers[i] = temp                i -= 1            i += 1

解法三：

先对列表进行排序，如果前后两个元素相同，则输出。

class Solution:    def duplicate(self , numbers ):        # write code here        if not numbers:            return -1        numbers.sort()        for i in range(len(numbers)-1):            if numbers[i] == numbers[i+1]:                return numbers[i]

转载地址：https://blog.csdn.net/sinat_42437278/article/details/118114879 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！