您好,登錄后才能下訂單哦!
1 題目
不修改數(shù)組找出重復(fù)的數(shù)字
在一個(gè)長(zhǎng)度為N+1的數(shù)組里面的所有數(shù)字都在范圍1~N范圍內(nèi),所以數(shù)組至少有一個(gè)數(shù)字是重復(fù)的,請(qǐng)找出重復(fù)數(shù)字,但是不能修改輸入的數(shù)組。
2 思路
思路1:
我們開辟一個(gè)新的數(shù)組,初始化為0,然后把原始數(shù)組每個(gè)數(shù)據(jù)的值作為下標(biāo),把新數(shù)組通過(guò)這個(gè)下標(biāo)數(shù)據(jù)取出來(lái),如果取出來(lái)是1,就說(shuō)明這個(gè)下標(biāo)數(shù)據(jù)重復(fù)了,如果不是,我們直接放進(jìn)去,然后進(jìn)行新數(shù)組值進(jìn)行++操作。
思路2:
比如數(shù)據(jù)1 2 2 3 4 5 6 7, 我們先找到中間的值(1 + 7) / 2 = 4;然后我們判斷數(shù)組里面每個(gè)元素 1到4有多少個(gè),如果有大于4個(gè)數(shù)的話,我們一定說(shuō)明重復(fù)數(shù)據(jù)在范圍1到4里面,反之在范圍4到7中,比如我們上面的數(shù)據(jù)1到4有5個(gè)數(shù)據(jù),我們說(shuō)明可以知道重復(fù)數(shù)據(jù)范圍是1到4,然后我們?cè)侔褦?shù)據(jù)切一刀,從1到4, 有點(diǎn)像二分法,以此類推,知道我們求出答案。
關(guān)鍵點(diǎn):
1)我們要個(gè)輔助函數(shù):需要知道數(shù)組中從范圍start到end的元素個(gè)數(shù)
2)循環(huán)條件是while(end >= start)
3) 退循環(huán)條件是在while里面,if(end == start) {通過(guò)輔助函數(shù)得到的個(gè)數(shù)大于1就返回這個(gè)start值} else {break;}
3 代碼實(shí)現(xiàn)
#include <iostream> using namespace std; int getCount(const int *a, int len, int start, int end) { if (a == NULL || len <= 0) { return 0; } int count = 0; for (int i = 0; i < len; ++i) { if (a[i] >= start && a[i] <= end) { ++count; } } return count; } int getResetNumber(const int *a, int len) { if (a == NULL || len <= 0) { return -1; } int start = 1, end = len - 1; //int mid = (end - start) / 2 + start; while (end >= start) { int mid = (end - start) / 2 + start; int count = getCount(a, len, start, mid); if (end == start) { if (count > 1) { return start; } else { break; } } if (count > (mid - start + 1)) { end = mid; } else { start = mid + 1; } } return -1; } int main() { std::cout << "請(qǐng)輸入數(shù)組的長(zhǎng)度" << std::endl; int len = 0; std::cin >> len; if (len <= 0) { std::cout << "數(shù)組的長(zhǎng)度不合法" << std::endl; return -1; } int *a = new int[len]; std::cout << "請(qǐng)分別輸入數(shù)組的每個(gè)數(shù)據(jù)" << std::endl; for (int i = 0; i < len; ++i) { std::cin >> a[i]; if (a[i] <= 0 || a[i] >= len) { std::cout << "輸入的數(shù)據(jù)有誤" << std::endl; return -1; } } //int count = getCount(a, len, 1, len - 1); int value = getResetNumber(a, len); if (value == -1) { std::cout << "沒(méi)有找到重復(fù)的數(shù)據(jù)" << std::endl; return -1; } std::cout << "其中一個(gè)重復(fù)的數(shù)據(jù)是" << value << std::endl; delete []a; return 0; }
4 運(yùn)行結(jié)果
請(qǐng)輸入數(shù)組的長(zhǎng)度
5
請(qǐng)分別輸入數(shù)組的每個(gè)數(shù)據(jù)
1
2
3
4
2
其中一個(gè)重復(fù)的數(shù)據(jù)是2
5 本質(zhì)和總結(jié)
在區(qū)間start~end里面,我們要縮小一半?yún)^(qū)間,我們直接找到start~end的中間數(shù)M = (start - end) / 2 + start,然后遍歷數(shù)組,如果在這個(gè)范圍的數(shù)據(jù)等于M 大于(M - start + 1)說(shuō)明這個(gè)段區(qū)間有重復(fù)數(shù)據(jù),反之?dāng)?shù)目重復(fù)數(shù)據(jù)在M+1到end區(qū)間,然后每次這切割,以此類推,所以這里要用到循環(huán),用循環(huán)就要條件,我們知道二分法這些操作條件是while(end >= start),既然有循環(huán),那我們必須找到跳出循環(huán)條件的條件在while循環(huán)里面 if (end == start) {輔助函數(shù)個(gè)數(shù) > 1} else {break;}
以上就是這篇文章的全部?jī)?nèi)容了,希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,謝謝大家對(duì)億速云的支持。如果你想了解更多相關(guān)內(nèi)容請(qǐng)查看下面相關(guān)鏈接
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。