•  
• #include 
         
          #include 
          
           /*    面试题3：数组中重复的数字：    问题：   在len长、值域为【1，len-1】的数组中找到重复的那个数字，不能修改原数组    解决：   哈希表，时间空间复杂度都是o(n)             二分查找，不断的查找重复的数字是在值域的前半区间内，还是在后半区间内             时间复杂度为o(nlgn), 空间复杂度为o(1)*/using namespace std;// 返回[low, up]范围内是否有重复数字bool check_repeat(const vector
           
             array_n, const int len, const int up,const int low){    int number = 0;    for(int i = 0; i < len; i++)    {        if (array_n[i]>=low && array_n[i]<=up)            number++;    }    if (up-low+1 < number) return true;    else return false;}//在len长、值域为【1，len-1】的数组中找到重复的那个数字int getduplication(const vector
            
              array_n, const int len){    if (array_n.size() == 0)        return -1;    for (int i = 0; i < len; i++)        if (array_n[i] > len-1 || array_n[i] < 1) return -2;    int up = len-1;    int low = 0;    while(true)    {        if (up == low)            break;        if (check_repeat(array_n, len, up, low/2+up/2))            low = low/2+up/2;        else            up = low/2+up/2-1;    }    return up;}int main(void){    int len;    cin >> len;    vector
             
               array_n(len, 0);    for (int i = 0; i < len; i++)        cin >> array_n[i];    int duplication = getduplication(array_n, len);    if (duplication == -1)        cout << "输入的数组为空";    else if (duplication == -2)        cout << "输入的数组的值域不在【" << 1 << "," << len-1 << "】之间";    else        cout << duplication;    return 0;}