image.png

解法一：類似于桶排序，建立0-n-1桶，如果遍歷時(shí)該桶值不為0，則重復(fù)。

# -*- coding:utf-8 -*-
class Solution:
    # 這里要特別注意~找到任意重復(fù)的一個(gè)值并賦值到duplication[0]
    # 函數(shù)返回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

解法二: 首先排序，然后遍歷，是否與前一個(gè)數(shù)字相等

# -*- coding:utf-8 -*-
class Solution:
    # 這里要特別注意~找到任意重復(fù)的一個(gè)值并賦值到duplication[0]
    # 函數(shù)返回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

解法三：書(shū)上的思路，p39

# -*- coding:utf-8 -*-
class Solution:
    # 這里要特別注意~找到任意重復(fù)的一個(gè)值并賦值到duplication[0]
    # 函數(shù)返回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