题目描述 牛客网

• 在一个长度为 n+1 的数组里的所有数字都在 1~n 的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为 8 的数组 {2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字 2 或者 3

解题思路

• 思路一 剑指Offer 40
• 思路二 建立哈希表，每次循环去map中查找，如果找不到则进入map，找到则返回这个重复数值

代码

#include<iostream>
using namespace std;

bool getCount(int a[], int left, int right, int length){
    int i;
    int sum = 0;

    for(i = 0; i < length; i++){
        if(left <= a[i] && a[i] <= right){
            sum++;
        }
    }

    if(sum > (right - left + 1)){
        return true;
    }
    else{
        return false;
    }
}

int getDuplication(int a[], int left, int right, int length){
    int mid = (left + right) / 2;
    bool ll;

    ll = getCount(a, left, mid, length);

    if((right - left) == 1){
        if(ll){
          return left;
        }
        else{
          return right;
        }
    }

    if(ll){
        return getDuplication(a, left, mid, length);
    }
    else{
        return getDuplication(a, mid+1, right, length);
    }
}

int main(){
    int a[] = {2, 2, 5, 4, 3, 2, 6, 7};
    int left = 1, right = 7;
    int length = 8;

    cout<<getDuplication(a, left, right, length)<<endl;
}

总结展望

• 思路甚好，值得学习，看书上代码逻辑复杂，直接看思路自己写的。感觉我写的代码比书上的容易理解..