找出數(shù)組中重復的數(shù)字
在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)次哈。 數(shù)組中某些數(shù)字是重復的溅话，但不知道有幾個數(shù)字是重復的。也不知道每個數(shù)字重復幾次收夸。請找出數(shù)組中任意一個重復的數(shù)字蜗顽。 例如布卡，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}，那么對應的輸出是重復的數(shù)字2或者3
下面是幾個解決這個問題的思路
解決這個問題的簡單的辦法是把輸入的數(shù)組排序雇盖。然后從排序的數(shù)組中找出重復的元素忿等。從頭到位掃描一遍即可。用一個變量始終記錄著上一個元素崔挖。比較當前元素和上一個元素贸街。 排序一個長度為n的數(shù)組需要O(nlogn)的時間。
我們還可以使用Hash表來解決這個問題狸相。創(chuàng)建一個Hash表薛匪，從頭到尾遍歷一遍。Hash表沒有的話則加入hash脓鹃，有的話則Value+1逸尖。這個算法的時間復雜度是O(n),但是它提高時間效率是以創(chuàng)建一個大小為O(n)的哈希表為代價的。
-
還有一種方法是我們注意到0-n-1的范圍瘸右，如果沒有重復數(shù)字娇跟，那么排序之后數(shù)字i將出現(xiàn)在下標i的位置上，但是如果存在的話尊浓，某些位置就可能存在多個數(shù)組逞频，有的位置就可能不存在數(shù)字纯衍。
解決這個問題的思路栋齿。從頭到尾掃描，比較m和位置i的關系襟诸。如果相等則掃描下一個瓦堵，如果不等的話，m和下標m的元素互換歌亲。然后繼續(xù)執(zhí)行菇用。先比較位置和數(shù)字自身的關系，如果相同則掃描下一個陷揪。如果等于的話則找到了惋鸥。如果不等的話杂穷，則繼續(xù)互換。
bool dumplcate(int numbers[],int length,int*duplication){
if (numbers == nullptr||length<=0) {
return false;
}
for (int i= 0; i<length; i++) {
if (numbers[i]<0||numbers[i]>=length) {
return false;
}
}
for (int i=0; i<length; i++) {
while (numbers[i] != i) { //只要下標和當前原色不相等卦绣，就繼續(xù)執(zhí)行
int m = numbers[i];
if (m == numbers[m]) {
*duplication = m;
return true;
}
int transfer = numbers[m];
numbers[i] = transfer;
numbers[m] = m;
}
}
return false;
}