題目1：在一個(gè)長(zhǎng)度為
的數(shù)組里艇纺，所有數(shù)字都在![[0, N-1]](https://math.jianshu.com/math?formula=%5B0%2C%20N-1%5D)
的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的完疫，但是不知道有幾個(gè)數(shù)字重復(fù)了，也不知道每個(gè)數(shù)字重復(fù)了幾次债蓝。請(qǐng)找出數(shù)組的任意一個(gè)重復(fù)的數(shù)字壳鹤。
解析：在這道題的背景下，如果把數(shù)字放到他的下標(biāo)對(duì)應(yīng)的位置饰迹，也就是把一個(gè)數(shù)組還原成一個(gè)遞增數(shù)列芳誓，只不過每一個(gè)下標(biāo)對(duì)應(yīng)的數(shù)字就是下標(biāo)本身的話，如果這個(gè)數(shù)組里面沒有重復(fù)數(shù)字啊鸭，那么還原可以完美的完成锹淌。但是由于數(shù)組內(nèi)有重復(fù)數(shù)字，那么在還原的過程中赠制，就會(huì)發(fā)現(xiàn)當(dāng)需要把它放在合適的位置的時(shí)候赂摆，這個(gè)位置上已經(jīng)有一個(gè)相同的數(shù)字了。例如 {0,1,2,2,4,5,6}钟些，下標(biāo)為 3 的 2 應(yīng)該放在下標(biāo)為 2 的位置上烟号，但是這個(gè)地方已經(jīng)有一個(gè) 2 了。遇到這種情況厘唾，我們就立即可以返回這個(gè)數(shù)字褥符。
使用這個(gè)思路龙誊，我們就可以寫出算法了抚垃。只要當(dāng)前位置上的數(shù)字和下標(biāo)不相等，那就看看這個(gè)數(shù)字應(yīng)該去的地方有沒有同樣的數(shù)字趟大。如果發(fā)現(xiàn)那個(gè)地方的數(shù)字和下標(biāo)是相同的鹤树，那就說明這個(gè)地方的數(shù)字是重復(fù)的，就可以返回了逊朽。如果那邊的也不對(duì)的話罕伯，就把當(dāng)前位置上的數(shù)字放到它應(yīng)該的位置，把那個(gè)位置上的數(shù)字交換過來叽讳。然后繼續(xù)比較當(dāng)前位置上的數(shù)字和下標(biāo)追他，直到當(dāng)前位置上的數(shù)字和下標(biāo)相等。接著對(duì)下一個(gè)位置進(jìn)行同樣的處理岛蚤。如果每一位都是合適的邑狸，那就說明這個(gè)數(shù)組沒有重復(fù)數(shù)字。
上面的算法是沒有問題的涤妒，但是你可能有疑問：如果這個(gè)位置永遠(yuǎn)都換不來那個(gè)合適的數(shù)字呢单雾？例如，{1,3,2,4,3} 沒有 0 這個(gè)數(shù)字，那么怎么辦呢硅堆？答案是不影響屿储。檢查第 0 位的時(shí)候，會(huì)把第 0 位的 1 和第 1 位的 3 互換渐逃。這個(gè)時(shí)候第 1 位就是 1够掠，沒毛病。接著會(huì)把第 0 位的 3 和第 3 位的 4 互換朴乖，這個(gè)時(shí)候第 3 位也是 3祖屏，沒毛病。接著會(huì)把第 0 位的 4 和第 4 位的 3 互換买羞，發(fā)現(xiàn)第 3 位已經(jīng)是 3 了袁勺，此時(shí)返回 3⌒笃眨看到?jīng)]有期丰？即便換不到該有的數(shù)字，在交換的過程中也是可以找到重復(fù)的數(shù)字的吃挑。
答案：
// 時(shí)間復(fù)雜度 O(N)钝荡，空間復(fù)雜度 O(1)
int findDuplicate(int array[], int length)
{
if (nullptr == array || length <= 0)
return -1;
for (int i=0; i<length; ++i)
{
if (array[i]<0 || array[i]>length-1)
return -1;
}
for (int i=0; i<length; ++i)
{
while (array[i] != i)
{
if (array[i] == array[array[i]])
{
return array[i];
}
else
{
int temp = array[i];
array[i] = array[array[i]];
array[temp] = temp;
}
}
}
return -1;
}
題目2：不修改數(shù)組的情況下找出重復(fù)的數(shù)字。在一個(gè)長(zhǎng)度為
的數(shù)組里舶衬，所有的數(shù)字都在![[1,N]](https://math.jianshu.com/math?formula=%5B1%2CN%5D)
的范圍內(nèi)埠通。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字，但不能修改輸入的數(shù)組逛犹。
解析：上面的那個(gè)算法會(huì)修改原有的數(shù)組端辱。如果要求不修改原有數(shù)組，也不能使用 O(n) 的空間來復(fù)制一份虽画，可以犧牲一點(diǎn)時(shí)間復(fù)雜度舞蔽，那就用下面這個(gè)算法。
首先我們考慮一個(gè)事實(shí)：如果統(tǒng)計(jì)數(shù)組里面的數(shù)字码撰，在區(qū)間 [1,N] 的范圍內(nèi)如果出現(xiàn)超過了N個(gè)數(shù)渗柿，那就說明一定至少有一個(gè)數(shù)字重復(fù)了。就像一年有 365 天 (不考慮平閏年)脖岛，那么 366 個(gè)人中一定至少有兩個(gè)人的生日重復(fù)了朵栖。
我們可以使用這個(gè)方法來二分的統(tǒng)計(jì)數(shù)字的出現(xiàn)個(gè)數(shù)。題目說所有的數(shù)字都在 [1,N] 的范圍內(nèi)柴梆，那么我就統(tǒng)計(jì) [1,N/2] 和 [N/2+1,N] 的數(shù)字出現(xiàn)次數(shù)陨溅，哪一個(gè)次數(shù)超過 N/2，哪一個(gè)就一定有重復(fù)的數(shù)字轩性。接下來在重復(fù)的那個(gè)區(qū)間內(nèi)繼續(xù)二分統(tǒng)計(jì)声登，直到區(qū)間退化為一個(gè)數(shù)字狠鸳，而且這個(gè)數(shù)字出現(xiàn)的次數(shù)大于1，那么就找到了這個(gè)數(shù)字悯嗓。每統(tǒng)計(jì)一次出現(xiàn)次數(shù)會(huì)占用 O(N) 的時(shí)間件舵。二分的統(tǒng)計(jì)最多有 log(N) 次統(tǒng)計(jì)。所以時(shí)間復(fù)雜度為 O(NlogN)脯厨。
舉個(gè)例子铅祸。{1,2,3,3,4,5,6,7}，長(zhǎng)度為 8合武，每個(gè)數(shù)字都在 [1,7] 的范圍內(nèi)临梗。先統(tǒng)計(jì) [1,3] 的，有四次稼跳，[4,7] 的盟庞，也有四次。那么繼續(xù)統(tǒng)計(jì) [1,3]汤善。1 出現(xiàn)了一次什猖，[2,3] 出現(xiàn)了三次。繼續(xù)統(tǒng)計(jì) [2,3]红淡。2 出現(xiàn)了一次不狮，3 出現(xiàn)了兩次，BOOM在旱，返回 3摇零。
答案：
//時(shí)間復(fù)雜度為 O(NlogN)，空間復(fù)雜度為 O(1)
int count(const int array[], int length, int beg, int end)
{
if (nullptr==array || length<=0)
return -1;
int cnt = 0;
for (int i=0; i<length; ++i)
{
if (array[i]>=beg && array[i]<=end)
++cnt;
}
return cnt;
}
int findDuplicate(const int array[], int length)
{
if (nullptr==array || length<=0)
return -1;
for (int i=0; i<length; ++i)
{
if (array[i]<1 || array[i]>length)
{
return -1;
}
}
int beg = 1, end = length-1;
while (beg<=end)
{
int mid = ((end-beg)>>1) + beg;
int cnt = count(array, length, beg, mid);
if (beg==end)
{
if (cnt>1) return beg;
else return -1;
}
if (cnt>(mid-beg+1)) end = mid;
else beg = mid+1;
}
return -1;
}
