開始學(xué)算法，首先明確目標(biāo)，目標(biāo)是能做算法題過面試

第一個問題：教材，我買的是劍指offer

第二個問題：題庫，我用的是?？途W(wǎng)的題庫 https://www.nowcoder.com/

學(xué)習(xí)思路：看教程，做例題，做筆記，多復(fù)習(xí)，做模擬題，考前(面試前)沖刺刷熱題

要求：熟悉每一道題，手打默寫，日后不忘

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

進(jìn)階：時間復(fù)雜度$O(n)$，空間復(fù)雜度$O(n)$

題目關(guān)鍵：數(shù)字大小不超過數(shù)組長度(數(shù)字只會從數(shù)組下標(biāo)里選)，重復(fù)的數(shù)字不用全部找出。

解題思路：假如沒有重復(fù)數(shù)字，例如數(shù)組[0,1,2]，下標(biāo)和數(shù)字必是一一對應(yīng)。如果有重復(fù)數(shù)字，例如[0,1,1]，數(shù)組[1] 會對應(yīng)2個1。

我們可以重排這些數(shù)字，讓數(shù)值與數(shù)組下標(biāo)重回一一對應(yīng)的狀態(tài)。遍歷這個數(shù)組，判斷數(shù)值與數(shù)組下標(biāo)是否相同，如果不同就放回正確的坐標(biāo)。

例如，數(shù)組[0]位置數(shù)值是3，那就把3放回?cái)?shù)組[3]，將3放回?cái)?shù)組[3]的時候判斷3是否等于數(shù)組[3]位置上的數(shù)值，如果相等就返回3，程序結(jié)束，如果不相等繼續(xù)比較數(shù)組[0]位置是不是0，不是則重復(fù)把數(shù)組[0]位置的數(shù)值放回正確的位置并判斷。

下面舉2個例子：

有個數(shù)組，list=[0,1,1];? ? 0 與 下標(biāo)0?相等。下一個 1 與 下標(biāo)1?相等。下一個 1 與??下標(biāo) 2 不相等，判斷 1 與 list[2] 是否相等，結(jié)果是相等的 返回1 程序結(jié)束

有個數(shù)組，list=[2,0,1];? ?2 與 下標(biāo)0?不相等。判斷 2 == list[2]，不相等。交換2者位置 list=[0,2,1] 判斷 0 與 下標(biāo)0 相等， 繼續(xù)下一個，2 與 下標(biāo)1 不相等 ，判斷2與list[2]是否相等，不相等 交換位置 list=[0,1,2]。繼續(xù)下一步他也找不到重復(fù)的 循環(huán)遍歷結(jié)束 返回-1

算法實(shí)現(xiàn)：