欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

關于C++數組中重復的數字

 更新時間：2021年11月03日 10:47:09   作者：zx255  
這篇文章主要介紹得是關于C++數組中重復的數字，文章以問題描述得形式，對問題展開分析用不同得方法去解決問題并附上方法得詳細代碼,需要的朋友可以參考以下文章得具體內容

1、題目描述

找出數組中重復的數字。在一個長度為 n 的數組 nums 里的所有數字都在 0～n-1 的范圍內。數組中某些數字是重復的，但不知道有幾個數字重復了，也不知道每個數字重復了幾次。

請找出數組中任意一個重復的數字。

題目示例：

  • 輸入：[2, 3, 1, 0, 2, 5, 3]
  • 輸出：2 或 3

1.1 方法一：排序

先對數組進行排序
此時從頭到尾掃一遍數組就可以了
時間復雜度 O ( l o g 2 n ) O(log_2n) O(log2​n)

代碼示例：

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 方法二：哈希表

  • 從頭到尾掃一遍數組
  • 每掃到一個數字，判斷哈希表里是否包含了該數字
  • 如果還沒有，就把它加入哈希表中
  • 如果已經存在該數字，就找到了一個重復的數字。

時間復雜度 O ( n ) O(n) O(n) 、空間復雜度 O ( n ) O(n) O(n) ，提高時間效率是以創(chuàng)建一個 O ( n ) O(n) O(n) 的哈希表為代價的。

代碼示例：

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 方法三：數組位置交換

  • 從頭到尾掃描數組
  • 當掃描的數組下標為 i 時，判斷i這個位置的數字 (m) 是否等于 i 本身
  • 若是則掃描下一個數字
  • 若不是則判斷 m 和 下標為 m 的數字是否相同 (v[i] == v[v[i]])
  • 若相同則返回，循環(huán)結束
  • 若不同則把第 i 個數字 (m) 和 第 m 個數字交換
  • 然后重復這個過程，直至循環(huán)結束

時間復雜度為 O ( n ) O(n) O(n) ，空間復雜度為 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) // 數字必須在 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、題目升級

長度為 n+1 的數組，所有的數都在 1 ~ n 的范圍內，因此數組中至少有一個數字是重復的。找出數組中 任意一個 重復的數字，但 不能修改輸入的數組。

題目示例：

  • 輸入：[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 方法二：輔助數組

  • 創(chuàng)建一個長度為 n+1 的輔助數組，然后逐一的把原數組的每個數字復制到輔助數組中
  • 若原數組中 被復制的數字 是 m，則把它復制到輔助數組中下標為 m 的位置

時間復雜度為 O ( n ) O(n) O(n) ，空間復雜度為 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 的數字從中間的數字 分成兩部分，即分成 1 ~ m 和 m+1 ~ n

  • 若 1 ~ m 的數字，在整個數組上的數目超過 m，即超過該區(qū)間的長度，那么這一半的區(qū)間里一定包含重復的數字
  • 否則，另一半 m+1 ~ n 區(qū)間里一定包含重復的數字

繼續(xù)把包含重復數字的區(qū)間一分為二，直到找到一個重復的數字

時間復雜度為 O ( n l o g n ) O(nlog_n) O(nlogn​)，空間復雜度為 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);  // 這種賦值方式不會導致vector自動擴展內部大小

    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){    // 有兩個警告（auto是C++_11的擴展）
        cout << a << ' ';
    }
    */
    return 0;
}

到此這篇關于關于C++數組中重復的數字的文章就介紹到這了,更多相關C++數組中重復數字內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

注：文章轉自微信公眾號：Coder梁（ID：Coder_LT）

相關文章

  • Opencv 馬賽克和毛玻璃效果與圖片融合的實現

    Opencv 馬賽克和毛玻璃效果與圖片融合的實現

    這篇文章主要為大家詳細介紹了通過OpenCV實現馬賽克和毛玻璃濾鏡效果與圖片的融合，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2021-11-11
  • Qt編寫提示進度條的實現示例

    Qt編寫提示進度條的實現示例

    進度條在很地方都可以使用到，Qt自帶的進度條或者操作系統(tǒng)的進度條樣式，不夠炫，本文就介紹一下Qt編寫自定義控件的提示進度條的實現示例，感興趣的可以了解一下
    2021-12-12
  • C語言的位段與枚舉詳解

    C語言的位段與枚舉詳解

    這篇文章主要為大家詳細介紹了C語言的位段與枚舉，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
    2022-02-02
  • Qt 事件過濾器的具體實現

    Qt 事件過濾器的具體實現

    事件過濾器，見名之意，就是將事件過濾一遍，將不需要的事件都清除掉，剩下需要的事件進行操作。本文詳細的介紹了Qt 事件過濾器的具體實現，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
    2022-04-04
  • C++ std::condition_variable 條件變量用法解析

    C++ std::condition_variable 條件變量用法解析

    condition_variable（條件變量）是 C++11 中提供的一種多線程同步機制,它允許一個或多個線程等待另一個線程發(fā)出通知,以便能夠有效地進行線程同步,這篇文章主要介紹了C++ std::condition_variable 條件變量用法,需要的朋友可以參考下
    2023-09-09
  • C++?Cartographer的入口node main詳細講解

    C++?Cartographer的入口node main詳細講解

    這篇文章主要介紹了C++Node類Cartographer的入口node main，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習吧
    2023-03-03
  • C語言中 “_at()” 特殊地址定位詳解

    C語言中 “_at()” 特殊地址定位詳解

    這篇文章主要介紹了C語言中 “_at()” 特殊地址定位詳解的相關資料,需要的朋友可以參考下
    2017-05-05
  • Cocos2d-x保存用戶游戲數據之XML文件是否存在問題判斷方法

    Cocos2d-x保存用戶游戲數據之XML文件是否存在問題判斷方法

    這篇文章主要介紹了Cocos2d-x保存用戶游戲數據之XML文件是否存在問題判斷方法,請注意代碼中包含大量注釋,需要的朋友可以參考下
    2014-09-09
  • 詳解QListWidget如何實現自定義Item效果

    詳解QListWidget如何實現自定義Item效果

    這篇文章主要為大家介紹了如何通過QListWidget實現自定義Item效果，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起了解一下
    2022-04-04
  • C++實現酒店管理系統(tǒng)

    C++實現酒店管理系統(tǒng)

    這篇文章主要為大家詳細介紹了C++實現酒店管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2021-08-08

最新評論