劍指Offer第二版 面試題3 心得
數(shù)組中重復(fù)的數(shù)字：
題目一：找出數(shù)組中重復(fù)的數(shù)字。
在一個(gè)長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)儿奶。 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的。也不知道每個(gè)數(shù)字重復(fù)幾次蹂楣。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字赏参。 例如志笼，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}，那么對(duì)應(yīng)的輸出是重復(fù)的數(shù)字2或者3把篓。
先附上代碼
首先籽腕，兩個(gè)條件判斷：
1.數(shù)組不能為空，長度不能小于0.否則return false
2.長度為n的這個(gè)數(shù)組值范圍在0~n-1纸俭，若不滿足皇耗，返回false
實(shí)現(xiàn)思想：
重排數(shù)組，數(shù)字i將出現(xiàn)在下標(biāo)i的位置揍很，但因數(shù)組中有重復(fù)數(shù)字郎楼，所以肯定有不滿足的時(shí)候。
首先窒悔，排序過程呜袁，遍歷數(shù)組，當(dāng)數(shù)組下標(biāo) i 與數(shù)組的值 m 不等時(shí)简珠，將下標(biāo)是m的數(shù)組中的值與下標(biāo)i的數(shù)組的值m交換阶界。
這個(gè)過程中，要先判斷聋庵，一旦下標(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è)長度為n+1的數(shù)組里的所有數(shù)字都在1~n的范圍內(nèi)，所以數(shù)組中至少有一個(gè)數(shù)字是重復(fù)的塔逃，請(qǐng)找出任意一個(gè)重復(fù)的數(shù)字讯壶，但不能修改輸入的數(shù)組。例如湾盗，如果輸入長度為8的數(shù)組{2,3,5,4,3,2,6,7},那么對(duì)應(yīng)的輸出是重復(fù)的數(shù)字2或者3.
附上代碼
解題思路：
應(yīng)用二分查找思想伏蚊，例如長度為8的數(shù)組，數(shù)組值的范圍必定為1~7之間格粪，將其值范圍二分躏吊，1~4和5~7，查找整個(gè)數(shù)組的值在1~4范圍內(nèi)有幾個(gè)帐萎，如果大于4個(gè)比伏，則說明重復(fù)的值一定在這個(gè)范圍內(nèi)，縮小范圍重復(fù)操作繼續(xù)查找疆导，直到找到最終重復(fù)的值赁项。
