3.数组中重复的数字
程序员文章站
2022-05-09 14:49:13
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。 class solution: ......
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
class solution:
def duplicate(self,list,duplication):
for x in range(len(list)):
while list[x] != x:
if list[list[x]] == list[x]:
duplication.append(list[x])
return true
else:
list[list[x]],list[x] = list[x],list[list[x]]
return false
#这样的话就可以不用开辟空间,减少空间复杂度。算是最完美的解决方法