- 在一个长度为 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;
}
总结展望
- 思路甚好，值得学习，看书上代码逻辑复杂，直接看思路自己写的。感觉我写的代码比书上的容易理解..
