如何用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(vectorint>
    &
 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) ，提高时间效率是以创建一个 O ( n ) O(n) O(n) 的哈希表为代价的。

代码示例：

int repeatNum(vectorint>
    &
 v){
    
    if(v.empty()) return -1;
    
    mapint, 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]])
• 若相同则返回，循环结束
• 若不同则把第 i 个数字 (m) 和 第 m 个数字交换
• 然后重复这个过程，直至循环结束

时间复杂度为 O ( n ) O(n) O(n) ，空间复杂度为 O ( 1 ) O(1) O(1)

代码示例：

int repeatNum(vectorint>
    &
 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(vectorint>
    &
 v){
    
    if(v.empty()) return -1;
    
    mapint, 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 方法二：辅助数组

• 创建一个长度为 n+1 的辅助数组，然后逐一的把原数组的每个数字复制到辅助数组中
• 若原数组中 被复制的数字 是 m，则把它复制到辅助数组中下标为 m 的位置
  

时间复杂度为 O ( n ) O(n) O(n) ，空间复杂度为 O ( n ) O(n) O(n)

代码示例：

int repeatNum(vectorint>
    &
 v){
    
    int len = v.size();
    
    vectorint>
     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，即超过该区间的长度，那么这一半的区间里一定包含重复的数字
• 否则，另一半 m+1 ~ n 区间里一定包含重复的数字
  

继续把包含重复数字的区间一分为二，直到找到一个重复的数字

时间复杂度为 O ( n l o g n ) O(nlog_n) O(nlogn​)，空间复杂度为 O ( 1 ) O(1) O(1)

代码示例：

int countRange(vectorint>
    &
 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(vectorint>
    &
 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(vectorint>
    &
 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}
    ;
    
    vectorint>
     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;

}
    

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！