題目描述：
在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復的，但不知道有幾個數(shù)字是重復的。也不知道每個數(shù)字重復幾次。請找出數(shù)組中任意一個重復的數(shù)字。 例如，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}，那么對應的輸出是第一個重復的數(shù)字2。

公司主營業(yè)務：網(wǎng)站制作、成都網(wǎng)站制作、移動網(wǎng)站開發(fā)等業(yè)務。幫助企業(yè)客戶真正實現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。成都創(chuàng)新互聯(lián)是一支青春激揚、勤奮敬業(yè)、活力青春激揚、勤奮敬業(yè)、活力澎湃、和諧高效的團隊。公司秉承以“開放、自由、嚴謹、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。成都創(chuàng)新互聯(lián)推出靜海免費做網(wǎng)站回饋大家。

# -*- coding: utf-8 -*-
# @Time         : 2019-04-15 17:31
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : duplicate_num_in_array.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

class Solution:
    # 這里要特別注意~找到任意重復的一個值并賦值到duplication[0]
    # 函數(shù)返回True/False
    def duplicate(self, numbers, duplication):
        # 完整的做法是先進行輸入合法性檢查，然后將每個數(shù)字放到它應該在的下標，在每次交換之前先檢查該下標是否已保存了正確的數(shù)字，
        # 如果是則該數(shù)字是一個重復數(shù)字
        # 時間復雜度O(n)，空間復雜度O(1)。由于每個數(shù)字最多交換兩次就可以放到正確的位置(第一次被從不正確的位置換到另一個不正確的位置，
        # 然后第二次就會專門為它找到屬于它的位置，因此最多是兩次)，也就是最多比較2n次，即時間復雜度是O(n)
        if not numbers:
            return False
        if max(numbers) >= len(numbers) or min(numbers) < 0:
            return False

        for i in range(len(numbers)):
            while numbers[i] != i:
                if numbers[numbers[i]] == numbers[i]:
                    duplication[0] = numbers[i]
                    return True
                else:
                    # 注意這樣交換會出現(xiàn)問題，需要先保存一個中間結(jié)果，不能直接交換，
                    # 否則當處理numbers[numbers[i]]的時候會找不到正確的下標
                    # numbers[i], numbers[numbers[i]] = numbers[numbers[i]], numbers[i]
                    temp = numbers[i]
                    numbers[i] = numbers[numbers[i]]
                    numbers[temp] = temp

        return False

    def duplicate2(self, numbers, duplication):
        # duplicate1()需要對輸入數(shù)組進行修改，假如要求不修改輸入數(shù)組，那么可以借鑒二分查找的
        # 思想，逐步縮小重復數(shù)字所在的區(qū)間。

        # 但是這種方法不能確保找到所有重復的數(shù)字，
        # 如果counter(left, right) == right - left + 1，不能排除[left, right]有重復
        # 數(shù)字的情況，例如[2, 3, 5, 4, 3, 2, 6, 7]中，counter(1, 2) == 2，但是2其實是
        # 重復數(shù)字

        # 由于是借鑒了二分查找的思想，因此while需要循環(huán)logn次，counter需要n次運算
        # 故時間復雜度O(nlogn), 空間復雜度O(1)
        def counter(start, end):  # 統(tǒng)計numbers中處于[start, end]之間的數(shù)字個數(shù)
            count = 0
            for num in numbers:
                if start <= num <= end:
                    count += 1
            return count

        if not numbers:  # 輸入合法性判斷
            return False
        left, right = 0, len(numbers) - 1  # 初始區(qū)間為[0, n-1]
        while left <= right:
            mid = (left + right) >> 1
            cnt = counter(left, mid)
            # 需要注意這里的循環(huán)出口，如果不在循環(huán)內(nèi)判斷l(xiāng)eft==right的情況的話就需要在循環(huán)外面
            # 再判斷一次counter(left, left) == 1
            if left == right:
                if cnt > 1:
                    duplication[0] = left
                    return True
                break
            if cnt > mid - left + 1:
                # 由于是判斷了 [left, mid]是否存在重復，并不能排除mid就是重復的數(shù)字，
                # 因此right不能更新為mid - 1
                right = mid
            else:
                left = mid + 1

        return False

    def duplicate3(self, numbers, duplication):
        # 由于數(shù)組中的數(shù)字范圍已定，可以通過申請一個容量為數(shù)字范圍的數(shù)組然后建立哈希表進行去重
        # 時間復雜度O(n), 空間復雜度O(n)
        arr = [-1] * len(numbers)
        for num in numbers:
            if arr[num] == -1:
                arr[num] = num
            else:
                duplication[0] = num
                return True
        return False