筆者由于在找工作，所以近期最主要的任務(wù)就是準(zhǔn)備面試，不打無準(zhǔn)備之仗菠劝。只有你準(zhǔn)備充分了赊舶，那么你想要的機(jī)會才有機(jī)會入你懷中睁搭。
筆者會將準(zhǔn)備面試的學(xué)習(xí)過程記錄下來，方便自己復(fù)盤的同時也希望能給一道找工作的小伙伴們一些幫助笼平。筆者準(zhǔn)備的內(nèi)容大綱如下
妥妥的去面試之?dāng)?shù)據(jù)結(jié)構(gòu)與算法（一）
下面是本篇博客的正菜部分：
一园骆、找出數(shù)組中重復(fù)的數(shù)字
在一個長度為n的數(shù)組里的所有數(shù)字都在0~n-1的范圍內(nèi)。找出數(shù)組中任意一個重復(fù)的數(shù)字寓调。
注意：如果題目改成找出數(shù)組中重復(fù)的數(shù)字的話锌唾，就需要和面試官溝通，我是找出所有重復(fù)的數(shù)字還是只需要找出一個就好了夺英。
排序法
先把原數(shù)組進(jìn)行一次排序晌涕，再對排序好的數(shù)組從頭到尾進(jìn)行遍歷，很容易找到重復(fù)的數(shù)字痛悯，排序長度為n的數(shù)組需要O(nlogn)的時間余黎。
哈希表法
可以借助哈希表解決該問題，從頭到尾掃描該數(shù)組载萌，判斷該掃描到的數(shù)是否存在于該哈希表中惧财，如果不存在則放于該哈希表中，如果存在則為重復(fù)元素扭仁。這個算法的時間復(fù)雜度是O(n),但卻是以大小為O(n)的空間復(fù)雜度為代價垮衷。
交換法
如果沒有重復(fù)元素的話，那么重排該數(shù)組后乖坠，數(shù)字i會出現(xiàn)在下標(biāo)i的位置搀突。如果有重復(fù)元素的話，下標(biāo)i的位置可能不止一個數(shù)字熊泵，也可能沒有數(shù)字描姚。
從頭到尾掃描數(shù)組涩赢，掃描到下標(biāo)為i的數(shù)字（用m表示）看是否等于i，如果是則接著掃描下一個數(shù)字轩勘，如果不是筒扒，再拿它和下標(biāo)為m的那個數(shù)字比較，如果相等绊寻，則找到一個重復(fù)數(shù)字花墩，如果不相等，就和它交換澄步。重復(fù)這樣的操作冰蘑，直到找到重復(fù)的數(shù)字。
代碼實例：
如果不存在重復(fù)元素的話村缸，返回-1（具體返回的值可以和面試官溝通）
public int getDuplicateNumber(int[] numbers){
int len = numbers.length;
if(numbers == null || len <= 0) return -1;
for(int i=0;i<len;i++){
if(numbers[i] < 0 || numbers[i] > len-1)
return -1;
}
for(int i=0;i<len;i++){
while(numbers[i] != i){
if(numbers[i] == numbers[numbers[i]]){
return numbers[i]; //找到重復(fù)元素
}
else {
//交換numbers[i]和numbers[numbers[i]]的值
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
}
return -1;
}
二祠肥、不能修改數(shù)組找出重復(fù)的數(shù)字
在一個長度為n+1的數(shù)組里的所有數(shù)字都在1~n的范圍內(nèi)。找出數(shù)組中任意一個重復(fù)的數(shù)字梯皿。不能改變原數(shù)組并且不可借助大小超過O(n)的輔助空間仇箱。
二分法
因為長度是n+1，所以該數(shù)組至少有一個重復(fù)的數(shù)字东羹〖燎牛可以根據(jù)長度進(jìn)行一半一半的分割。比如長度為8的數(shù)組属提，把它分兩半：1-4,5-7权逗。先在數(shù)組中找在1-4范圍內(nèi)的數(shù)的個數(shù)，如果超過4個說明重復(fù)的數(shù)字在1-4中冤议。這樣就縮小了范圍斟薇，之后繼續(xù)二分，在數(shù)組中分別找1-2,3-4這兩組數(shù)字的個數(shù)恕酸，直到找到一個重復(fù)的數(shù)字堪滨。
public int getDuplicateNumber2(int[] numbers){
int len = numbers.length;
if(numbers == null || len <= 0) return -1;
int start = 1;
int end = len-1;
while(end >= start){
int middle = ((end - start) >> 1)+start;
int count = countRange(numbers,len,start,middle);
if(end == start){
if(count > 1) return start; //找到重復(fù)元素
else break;
}
if(count >(middle-start+1))
end = middle;
else
start = middle+1;
}
return -1;
}
private int countRange(int[] numbers, int len, int start, int end) {
if(numbers == null)
return 0;
int count = 0;
for(int i=0;i<len;i++){
if(numbers[i]>=start && numbers[i]<=end)
++count;
}
return count;
}
參考:劍指offer P39
面試系列的文章都放于 面試妥妥的 建議小伙伴們關(guān)注該專題
