關(guān)于C++數(shù)組中重復(fù)的數(shù)字
1、題目描述
找出數(shù)組中重復(fù)的數(shù)字。在一個(gè)長(zhǎng)度為 n 的數(shù)組 nums
里的所有數(shù)字都在 0~n-1 的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的,但不知道有幾個(gè)數(shù)字重復(fù)了,也不知道每個(gè)數(shù)字重復(fù)了幾次。
請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。
題目示例:
- 輸入:[2, 3, 1, 0, 2, 5, 3]
- 輸出:2 或 3
1.1 方法一:排序
先對(duì)數(shù)組進(jìn)行排序
此時(shí)從頭到尾掃一遍數(shù)組就可以了
時(shí)間復(fù)雜度 O ( l o g 2 n ) O(log_2n) O(log2n)
代碼示例:
int repeatNum(vector<int>& v){ if(v.empty()) return -1; int len = v.size(); sort(v.begin(), v.end()); for(int i = 1; i < len; i++){ if(v[i] == v[i-1]){ return v[i]; } } return -1; }
1.2 方法二:哈希表
- 從頭到尾掃一遍數(shù)組
- 每掃到一個(gè)數(shù)字,判斷哈希表里是否包含了該數(shù)字
- 如果還沒(méi)有,就把它加入哈希表中
- 如果已經(jīng)存在該數(shù)字,就找到了一個(gè)重復(fù)的數(shù)字。
時(shí)間復(fù)雜度 O ( n ) O(n) O(n)
、空間復(fù)雜度 O ( n ) O(n) O(n)
,提高時(shí)間效率是以創(chuàng)建一個(gè) O ( n ) O(n) O(n)
的哈希表為代價(jià)的。
代碼示例:
int repeatNum(vector<int>& v){ if(v.empty()) return -1; map<int, int> m; for(int i = 0; i < v.size(); i++){ if(m[v[i]]) return v[i]; else m[v[i]]++; } return -1; }
1.3 方法三:數(shù)組位置交換
- 從頭到尾掃描數(shù)組
- 當(dāng)掃描的數(shù)組下標(biāo)為 i 時(shí),判斷i這個(gè)位置的數(shù)字
(m)
是否等于 i 本身 - 若是則掃描下一個(gè)數(shù)字
- 若不是則判斷 m 和 下標(biāo)為 m 的數(shù)字是否相同
(v[i] == v[v[i]])
- 若相同則返回,循環(huán)結(jié)束
- 若不同則把第 i 個(gè)數(shù)字
(m)
和 第m
個(gè)數(shù)字交換 - 然后重復(fù)這個(gè)過(guò)程,直至循環(huán)結(jié)束
時(shí)間復(fù)雜度為 O ( n ) O(n) O(n)
,空間復(fù)雜度為 O ( 1 ) O(1) O(1)
代碼示例:
int repeatNum(vector<int>& v){ if(v.empty()) return -1; for(int i = 0; i < v.size(); ++i){ if(v[i] < 0 || v[i] > v.size()-1) // 數(shù)字必須在 0 ~ n-1 之間 return -1; } for(int i = 0; i < v.size(); ++i){ while(v[i] != i){ if(v[i] == v[v[i]]) return v[i]; swap(v[i], v[v[i]]); } } return false; }
2、題目升級(jí)
長(zhǎng)度為 n+1 的數(shù)組,所有的數(shù)都在 1 ~ n 的范圍內(nèi),因此數(shù)組中至少有一個(gè)數(shù)字是重復(fù)的。找出數(shù)組中 任意一個(gè) 重復(fù)的數(shù)字,但 不能修改輸入的數(shù)組。
題目示例:
- 輸入:[2, 3, 5, 4, 3, 2, 6, 7]
- 輸出:2 或 3
2.1 方法一:哈希表
方法同上:
int repeatNum(vector<int>& v){ if(v.empty()) return -1; map<int, int> m; for(int i = 0; i < v.size(); i++){ if(m[v[i]]) return v[i]; else m[v[i]]++; } return -1; }
2.2 方法二:輔助數(shù)組
- 創(chuàng)建一個(gè)長(zhǎng)度為 n+1 的輔助數(shù)組,然后逐一的把原數(shù)組的每個(gè)數(shù)字復(fù)制到輔助數(shù)組中
- 若原數(shù)組中 被復(fù)制的數(shù)字 是 m,則把它復(fù)制到輔助數(shù)組中下標(biāo)為 m 的位置
時(shí)間復(fù)雜度為 O ( n ) O(n) O(n)
,空間復(fù)雜度為 O ( n ) O(n) O(n)
代碼示例:
int repeatNum(vector<int>& v){ int len = v.size(); vector<int> v1(len); for(int i = 0; i < len; ++i){ if(v1[v[i]]) return v1[v[i]]; else v1[v[i]] = v[i]; } return -1; }
2.3 方法三:二分查找
將 1 ~ n 的數(shù)字從中間的數(shù)字 分成兩部分,即分成 1 ~ m
和 m+1 ~ n
- 若 1 ~ m 的數(shù)字,在整個(gè)數(shù)組上的數(shù)目超過(guò) m,即超過(guò)該區(qū)間的長(zhǎng)度,那么這一半的區(qū)間里一定包含重復(fù)的數(shù)字
- 否則,另一半 m+1 ~ n 區(qū)間里一定包含重復(fù)的數(shù)字
繼續(xù)把包含重復(fù)數(shù)字的區(qū)間一分為二,直到找到一個(gè)重復(fù)的數(shù)字
時(shí)間復(fù)雜度為 O ( n l o g n ) O(nlog_n) O(nlogn),
空間復(fù)雜度為 O ( 1 ) O(1) O(1)
代碼示例:
int countRange(vector<int>& v, int sz, int start, int end){ if(v.empty()) return 0; int count = 0; for(int i = 0; i < sz; ++i){ if(v[i] >= start && v[i] <= end){ ++count; } } return count; } int getrepeat(vector<int>& v){ if(v.empty()) return -1; int sz = v.size(); int start = 1, end = sz-1; while(end >= start){ int mid = start + ((end-start)>>1); int count = countRange(v, sz, 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; }
測(cè)試代碼:
bool duplicate(vector<int>& v, int **res){ if(v.empty()) return false; for(int i = 0; i < v.size(); ++i){ if(v[i] < 0 || v[i] > v.size()-1) return false; } for(int i = 0; i < v.size(); ++i){ while(v[i] != i){ if(v[i] == v[v[i]]) { *res = &v[i]; return true; } swap(v[i], v[v[i]]); } } return false; } int main(){ int arr[] = {2, 3, 5, 4, 3, 2, 6, 7}; vector<int> v(arr, arr+8); // 這種賦值方式不會(huì)導(dǎo)致vector自動(dòng)擴(kuò)展內(nèi)部大小 int* res = nullptr; if(duplicate(v, &res)) cout << *res << endl; else cout << '0' << endl; //cout << repeatNum(v) << endl; /* for(int i = 0; i < v.size(); i++){ if(i == 0) cout << v[i]; else cout << ' ' << v[i]; } cout << endl; for(auto a : v){ // 有兩個(gè)警告(auto是C++_11的擴(kuò)展) cout << a << ' '; } */ return 0; }
到此這篇關(guān)于關(guān)于C++數(shù)組中重復(fù)的數(shù)字的文章就介紹到這了,更多相關(guān)C++數(shù)組中重復(fù)數(shù)字內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
注:文章轉(zhuǎn)自微信公眾號(hào):Coder梁(ID:Coder_LT)
相關(guān)文章
Opencv 馬賽克和毛玻璃效果與圖片融合的實(shí)現(xiàn)
這篇文章主要為大家詳細(xì)介紹了通過(guò)OpenCV實(shí)現(xiàn)馬賽克和毛玻璃濾鏡效果與圖片的融合,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-11-11Qt編寫提示進(jìn)度條的實(shí)現(xiàn)示例
進(jìn)度條在很地方都可以使用到,Qt自帶的進(jìn)度條或者操作系統(tǒng)的進(jìn)度條樣式,不夠炫,本文就介紹一下Qt編寫自定義控件的提示進(jìn)度條的實(shí)現(xiàn)示例,感興趣的可以了解一下2021-12-12C++ std::condition_variable 條件變量用法解析
condition_variable(條件變量)是 C++11 中提供的一種多線程同步機(jī)制,它允許一個(gè)或多個(gè)線程等待另一個(gè)線程發(fā)出通知,以便能夠有效地進(jìn)行線程同步,這篇文章主要介紹了C++ std::condition_variable 條件變量用法,需要的朋友可以參考下2023-09-09C++?Cartographer的入口node main詳細(xì)講解
這篇文章主要介紹了C++Node類Cartographer的入口node main,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2023-03-03Cocos2d-x保存用戶游戲數(shù)據(jù)之XML文件是否存在問(wèn)題判斷方法
這篇文章主要介紹了Cocos2d-x保存用戶游戲數(shù)據(jù)之XML文件是否存在問(wèn)題判斷方法,請(qǐng)注意代碼中包含大量注釋,需要的朋友可以參考下2014-09-09詳解QListWidget如何實(shí)現(xiàn)自定義Item效果
這篇文章主要為大家介紹了如何通過(guò)QListWidget實(shí)現(xiàn)自定義Item效果,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起了解一下2022-04-04