劍指Offer第二版 面試題3 心得
數(shù)組中重復(fù)的數(shù)字：
題目一：找出數(shù)組中重復(fù)的數(shù)字。
在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的。也不知道每個(gè)數(shù)字重復(fù)幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。 例如，如果輸入長(zhǎng)度為7的數(shù)組{2,3,1,0,2,5,3}，那么對(duì)應(yīng)的輸出是重復(fù)的數(shù)字2或者3。
先附上代碼
首先，兩個(gè)條件判斷：
1.數(shù)組不能為空，長(zhǎng)度不能小于0.否則return false
2.長(zhǎng)度為n的這個(gè)數(shù)組值范圍在0~n-1，若不滿足，返回false
實(shí)現(xiàn)思想：
重排數(shù)組，數(shù)字i將出現(xiàn)在下標(biāo)i的位置，但因數(shù)組中有重復(fù)數(shù)字，所以肯定有不滿足的時(shí)候。
首先，排序過(guò)程，遍歷數(shù)組，當(dāng)數(shù)組下標(biāo) i 與數(shù)組的值 m 不等時(shí)，將下標(biāo)是m的數(shù)組中的值與下標(biāo)i的數(shù)組的值m交換。
這個(gè)過(guò)程中，要先判斷，一旦下標(biāo)為i的數(shù)組的值m等于下標(biāo)為m的數(shù)組的值，則表示m為重復(fù)的數(shù)字。
加入主函數(shù)
注意：
1.sizeof(data)=28,原因是data中有7個(gè)數(shù)，每個(gè)數(shù)值都是int類型，占4byte，共占7*4=28byte
sizeof(data[0])=4，一個(gè)int類型，4byte。
2.數(shù)組作為參數(shù)傳遞的時(shí)候，數(shù)組會(huì)自動(dòng)退化為同類型的指針。
3.將一個(gè)int類型的duplication傳參時(shí)，要注意加引入傳遞，形參聲明一個(gè)指針指向，即可隨時(shí)改變其值。
題目二：不修改數(shù)組找出重復(fù)的數(shù)字
在一個(gè)長(zhǎng)度為n+1的數(shù)組里的所有數(shù)字都在1~n的范圍內(nèi)，所以數(shù)組中至少有一個(gè)數(shù)字是重復(fù)的，請(qǐng)找出任意一個(gè)重復(fù)的數(shù)字，但不能修改輸入的數(shù)組。例如，如果輸入長(zhǎng)度為8的數(shù)組{2,3,5,4,3,2,6,7},那么對(duì)應(yīng)的輸出是重復(fù)的數(shù)字2或者3.
附上代碼
解題思路：
應(yīng)用二分查找思想，例如長(zhǎng)度為8的數(shù)組，數(shù)組值的范圍必定為1~7之間，將其值范圍二分，1~4和5~7，查找整個(gè)數(shù)組的值在1~4范圍內(nèi)有幾個(gè)，如果大于4個(gè)，則說(shuō)明重復(fù)的值一定在這個(gè)范圍內(nèi)，縮小范圍重復(fù)操作繼續(xù)查找，直到找到最終重復(fù)的值。
