劍指offer之C語言不修改數(shù)組找出重復(fù)的數(shù)字
1 題目
不修改數(shù)組找出重復(fù)的數(shù)字
在一個長度為N+1的數(shù)組里面的所有數(shù)字都在范圍1~N范圍內(nèi),所以數(shù)組至少有一個數(shù)字是重復(fù)的,請找出重復(fù)數(shù)字,但是不能修改輸入的數(shù)組。
2 思路
思路1:
我們開辟一個新的數(shù)組,初始化為0,然后把原始數(shù)組每個數(shù)據(jù)的值作為下標(biāo),把新數(shù)組通過這個下標(biāo)數(shù)據(jù)取出來,如果取出來是1,就說明這個下標(biāo)數(shù)據(jù)重復(fù)了,如果不是,我們直接放進去,然后進行新數(shù)組值進行++操作。
思路2:
比如數(shù)據(jù)1 2 2 3 4 5 6 7, 我們先找到中間的值(1 + 7) / 2 = 4;然后我們判斷數(shù)組里面每個元素 1到4有多少個,如果有大于4個數(shù)的話,我們一定說明重復(fù)數(shù)據(jù)在范圍1到4里面,反之在范圍4到7中,比如我們上面的數(shù)據(jù)1到4有5個數(shù)據(jù),我們說明可以知道重復(fù)數(shù)據(jù)范圍是1到4,然后我們再把數(shù)據(jù)切一刀,從1到4, 有點像二分法,以此類推,知道我們求出答案。
關(guān)鍵點:
1)我們要個輔助函數(shù):需要知道數(shù)組中從范圍start到end的元素個數(shù)
2)循環(huán)條件是while(end >= start)
3) 退循環(huán)條件是在while里面,if(end == start) {通過輔助函數(shù)得到的個數(shù)大于1就返回這個start值} else {break;}
3 代碼實現(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 << "請輸入數(shù)組的長度" << std::endl; int len = 0; std::cin >> len; if (len <= 0) { std::cout << "數(shù)組的長度不合法" << std::endl; return -1; } int *a = new int[len]; std::cout << "請分別輸入數(shù)組的每個數(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 << "沒有找到重復(fù)的數(shù)據(jù)" << std::endl; return -1; } std::cout << "其中一個重復(fù)的數(shù)據(jù)是" << value << std::endl; delete []a; return 0; }
4 運行結(jié)果
請輸入數(shù)組的長度
5
請分別輸入數(shù)組的每個數(shù)據(jù)
1
2
3
4
2
其中一個重復(fù)的數(shù)據(jù)是2
5 本質(zhì)和總結(jié)
在區(qū)間start~end里面,我們要縮小一半?yún)^(qū)間,我們直接找到start~end的中間數(shù)M = (start - end) / 2 + start,然后遍歷數(shù)組,如果在這個范圍的數(shù)據(jù)等于M 大于(M - start + 1)說明這個段區(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ù)個數(shù) > 1} else {break;}
以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,謝謝大家對腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請查看下面相關(guān)鏈接
相關(guān)文章
OpenCV圖像旋轉(zhuǎn)Rotate的詳細(xì)介紹
這篇文章主要介紹了OpenCV圖像旋轉(zhuǎn)Rotate,本文通過實例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-05-05詳解Matlab繪制3D玫瑰花的方法(內(nèi)附旋轉(zhuǎn)版本)
這篇文章主要為大家介紹了如何利用Matlab繪制3D版的玫瑰花以及旋轉(zhuǎn)版的3D玫瑰花,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以動手試一試2022-03-03C++ normal_distribution高斯正態(tài)分布函數(shù)的用法示例
高斯分布也稱為正態(tài)分布(normal distribution),常用的成熟的生成高斯分布隨機數(shù)序列的方法由Marsaglia和Bray在1964年提出,這篇文章主要給大家介紹了關(guān)于C++ normal_distribution高斯正態(tài)分布函數(shù)用法的相關(guān)資料,需要的朋友可以參考下2021-07-07C語言 超詳細(xì)介紹與實現(xiàn)線性表中的帶頭雙向循環(huán)鏈表
帶頭雙向循環(huán)鏈表:結(jié)構(gòu)最復(fù)雜,一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu),都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜,但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢,實現(xiàn)反而簡單2022-03-03