## 面试题4:找到数组中重复的数字[不修改数组]

#### 2.思路

（1）hash 时间复杂度：O(1) , 额外空间复杂度：O(n)
（2）二分 时间复杂度：O(nlogn)，额外空间复杂度：O(1) 【以mid作为划分值,统计此范围内数的个数,如果大于mid-st+1,则该区域肯定会有重复的数字,否则另外一半存在】

#### 3.code

```#include <iostream>
#include <string>
#include <string.h>
using namespace std;

int find_by_hash(const int arr[], int len)
{
if(arr == NULL || len <= 0) return -1;
int hash[len];
int res = -1;
for(int i = 0; i < len; ++i){
hash[arr[i]]++;
if(hash[arr[i]] > 1){
res = arr[i];
break;
}
}
return res;
}

//二分,
int range_count(const int arr[], int len, int st, int ed){
if(arr == NULL || len <= 0){
return 0;
}
int count = 0;
for(int i = 0; i < len; ++i){
if(arr[i] >= st && arr[i] <= ed){
count++;
}
}
return count;
}

int find_by_bin(const int arr[], int len)
{
if(arr == NULL ||len <= 0) return -1;
int st = 1;
int ed = len-1;
while(st <= ed){
int mid = st + (ed - st) / 2;
int count = range_count(arr,len,st,mid);
if(st == ed){
if(count > 1)
return st;
else
break;
}
if(count > (mid-st+1)){
ed = mid;
}else{
st = mid+1;
}
}
return -1;
}

int main()
{
int arr[] = {2,3,6,7,5,3,2,4};
int len = sizeof(arr)/sizeof(arr[0]);

cout <<"init arr:" << endl;
for(int i = 0; i < len; ++i){
cout << arr[i] << " ";
}
cout<<"\n";
int res1,res2;
res1 = find_by_hash(arr,len);
res2 = find_by_bin(arr,len);
cout << "res1: " << res1 << endl;
cout << "res2: " << res2 << endl;
cout <<"after find arr:" << endl;
for(int i = 0; i < len; ++i){
cout << arr[i] << " ";
}
return 0;
}```