找出數(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）

您可能感興趣的文章: