題目描述：不修改數(shù)組找出重復(fù)的數(shù)字

????????在一個長度為n+1的數(shù)組里的所有數(shù)字都在1~n的范圍內(nèi)，所以數(shù)組中至少有一個數(shù)字是重復(fù)的。找出數(shù)組中任意一個重復(fù)的數(shù)字，但不能修改輸入的數(shù)組。

解題思路：解法一，創(chuàng)建一個輔助數(shù)組，然后逐個復(fù)制進(jìn)去，就能找到有沒有重復(fù)，空間復(fù)雜度是O(n)。

解法二，長度為8的數(shù)組 值范圍是1-7，list=[2,2,1,0,4,5,3]。

取中間下標(biāo)3，統(tǒng)計數(shù)組中大于1小于3的值。

假如0-3下標(biāo)中沒重復(fù)的值，我們統(tǒng)計數(shù)組中大于等于1小于等于3的值的個數(shù)，肯定不會大于3。

假如0-3下標(biāo)中有重復(fù)的值，例如上數(shù)組，大于等于1小于等于3的值的個數(shù)，2,2,1,3一共4個，說明值1-3之間一定有重復(fù)的數(shù)字

縮小范圍，取下標(biāo)2作為中間下標(biāo)，下標(biāo)1-2之間 大于等于1小于等于2的個數(shù)，2,2,1大于 2個數(shù)字，范圍里只有2個數(shù)字，這2個數(shù)字之間的值查詢整個數(shù)組卻找出來3個，說明這2個數(shù)字之間必有重復(fù)

再縮小范圍到1個數(shù)字，取下標(biāo)1作為中間下標(biāo)， 查詢下標(biāo)1的值在數(shù)組里重復(fù)的次數(shù)，2,2結(jié)果是2，那么下標(biāo)1的值就是重復(fù)的值，輸出2，程序結(jié)束

算法實現(xiàn)：?

countRange會被調(diào)用O(logn)次，每次需O(n)時間，總時間復(fù)雜度為O(nlogn)