题目描述
- 假设一个单调递增的数组里的每个元素都是整数并且是唯一的
- 请编程实现一个函数，找出数组中任意一个数值等于其下标的元素
- 例如，在数组
{-3，-1，1，3，5} 中，数字 3 和它的下标相等
题目解读
代码
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
int GetNumbersSameAsIndexCore(vector<int>& data, int left, int right){
if(left <= right){
int index = (left + right) >> 1;
int mid = data[index];
if(mid > index){
right = index - 1;
}
else if(mid < index){
left = index + 1;
}
else{
return mid;
}
return GetNumbersSameAsIndexCore(data, left, right);
}
else{
return -1;
}
}
int GetNumbersSameAsIndex(vector<int> data) {
int length = data.size();
if(length == 0){
return 0;
}
return GetNumbersSameAsIndexCore(data, 0, length-1);
}
};
int main(){
Solution ss;
int len = 5;
int a[10] = {-3, -1, 1, 3, 5};
// int a[10] = {-3, -1, 1, 8, 5};
vector<int> data;
for(int i=0; i < len; i++){
data.push_back(a[i]);
}
int index = ss.GetNumbersSameAsIndex(data);
if(index == -1){
cout<<"没有和下标相等的元素"<<endl;
}
else{
cout<<"和下标相等的元素为： "<<index<<endl;
}
}
总结展望
