image.png
解法一：类似于桶排序，建立0-n-1桶，如果遍历时该桶值不为0，则重复。
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
l = [0]*(len(numbers))
for x in numbers:
if l[x] != 0:
duplication[0] = x
return True
l[x] = 1
return False
解法二: 首先排序，然后遍历，是否与前一个数字相等
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
numbers.sort()
for i in range(1, len(numbers)):
if numbers[i] == numbers[i-1]:
duplication[0] = numbers[i]
return True
return False
解法三：书上的思路，p39
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
if len(numbers) == 0:
return False
for i in range(len(numbers)):
while numbers[i] != i:
if numbers[i] == numbers[numbers[i]]:
duplication[0] = numbers[i]
return True
temp = numbers[i]
numbers[i], numbers[temp] = numbers[temp], numbers[i]
return False
