数组中重复的数字

法1

时间复杂度：O(N)
空间复杂度：O(N)

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        cnt = {} # dictionary
        for num in numbers:
            if num in cnt:
                if cnt[num] == 1:
                    duplication[0] = num
                    return True
            else:
                cnt[num] = 1
        return False

法2

时间复杂度：O(N)
空间复杂度：O(1)

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        for i in range(len(numbers)):
            if numbers[i] != i:
                if numbers[numbers[i]] == numbers[i]:
                    duplication[0] = numbers[i]
                    return True
                else:
                    tmp = numbers[numbers[i]]
                    numbers[numbers[i]] = numbers[i]
                    numbers[i] = tmp
        return False