關(guān)于C++數(shù)組中重復(fù)的數(shù)字
1、題目描述
找出數(shù)組中重復(fù)的數(shù)字。在一個(gè)長度為 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ù)字
- 如果還沒有，就把它加入哈希表中
- 如果已經(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è)過程，直至循環(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í)
長度為 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è)長度為 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ù)目超過 m，即超過該區(qū)間的長度，那么這一半的區(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;
}
測試代碼:
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)文章
這篇文章主要介紹了C++中模板(Template)的詳解及其作用介紹，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-06-06
C++ Opencv自寫函數(shù)實(shí)現(xiàn)膨脹腐蝕處理技巧
這篇文章主要介紹了C++ Opencv 自寫函數(shù)實(shí)現(xiàn)膨脹腐蝕處理,本文通過示例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-10-10
這篇文章主要給大家介紹了關(guān)于C++繼承的定義與注意事項(xiàng)的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05
C++?list容器merge算法的使用以及注意事項(xiàng)
這篇文章主要介紹了C++?list容器merge算法的使用以及注意事項(xiàng),具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-04-04
Qt中提供了強(qiáng)大的2D繪圖系統(tǒng),可以使用同一API實(shí)現(xiàn)在屏幕和繪圖設(shè)備上進(jìn)行繪制，本文就詳細(xì)的介紹了Qt繪制坐標(biāo)圖、柱狀圖、折線圖、餅圖、曲線圖、散點(diǎn)圖等，感興趣的可以了解一下2021-05-05
一般情況下，由鍵盤輸入的字符并沒有直接送入程序，而是被存儲(chǔ)在一個(gè)緩沖區(qū)當(dāng)中。下面這篇文章主要給大家介紹了關(guān)于C語言中輸入輸出流與緩沖區(qū)的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友可以參考下2018-09-09
在本篇文章里我們給大家分析了C#和C++編程語言中的類的相關(guān)知識(shí)點(diǎn)，正在學(xué)習(xí)的朋友們跟著操作下。2019-02-02
這篇文章主要為大家詳細(xì)介紹了C++隨機(jī)生成迷宮算法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-03-03
C++實(shí)現(xiàn)正態(tài)隨機(jī)分布的方法
本篇介紹了，使用c++實(shí)現(xiàn)正態(tài)隨機(jī)分布的實(shí)現(xiàn)方法。需要的朋友參考下2013-05-05
詳解Dijkstra算法原理及其C++實(shí)現(xiàn)
Dijkstra算法用于計(jì)算一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑。Dijkstra是一種按路徑長度遞增的順序逐步產(chǎn)生最短路徑的方法，是一種貪婪算法。本文將詳解Dijkstra算法原理及其C++實(shí)現(xiàn)，感興趣的可以了解一下2022-07-07