3. 数组中重复的数字

• 普通方法，空间复杂度是O(n)

class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        hashmap = {}
        for i,j in enumerate(numbers):
            if j in hashmap:
                duplication[0] = j
                return True
            hashmap[j] = i
        return False

• 利用数组的特性，空间复杂度是O（1）

  题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。

分析题目，由于数字都在[0,n-1]的闭区间内，所以可以遍历数组，用第i个数的数值作为它的索引，再将该索引对应的数值加n。（代码第7行和13行）当另一个相同数字出现时，它的索引指向的数字因为之前加过n所以一定会大于等于n。此时即可返回该数字。（10行）

需要考虑的是，由于有些数字的值是加过n的，当遍历到该数字时，用数值做索引会超出范围，此时需要将该数值减n得到它的初始值，由初始值作为索引。

相应的，如果题目是：

在一个长度为n的数组里的所有数字都在1到n的范围内。

我们可以修改条件，把+n换成*（-1），index变为abs[num]-1

class Solution:

    def duplicate(self, numbers, duplication):
        # write code here
        n = len(numbers)
        for i in range(n):
            index = numbers[i]
            if index >= n:
                index -= n
            if numbers[index] >= n:
                duplication[0] = index
                return True
            numbers[index] = numbers[index] + n
        return False

• 书上的做法，重排数组

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

扩展题目描述：
　　在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但是不能修改输入的数组。

• 利用二分法，时间复杂度是O（nlogn），空间复杂度是O（1）

  class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers):
        # write code here
        if not numbers:
            return False
        start = 1
        end = len(numbers) - 1
        while start <= end:
            mid = start + (end - start )//2
            count = self.countrange(start,mid,numbers)
            if start == end:
                if count > 1:
                    return start 
                else :
                    break
            if count > (mid - start + 1):
                end = mid
            else:
                start = mid + 1
        return -1
  
    def countrange(self,start,end,numbers):
        count = 0
        if not numbers:
            return False
        for i in numbers:
            if start <= i <= end:
                count = count + 1
        return count