题目描述
假设一个单调递增的数组里的每个元素都是整数并且是唯一的。
请编程实现一个函数找出数组中任意一个数值等于其下标的元素。
例如,在数组 [−3,−1,1,3,5] 中,数字 3 和它的下标相等。
样例
输入:[-3, -1, 1, 3, 5]
输出:3
注意:如果不存在,则返回-1。
算法
(二分) $O(logn)$
可以证明nums[i] - i 是单调递增数组,即转化为求数组 nums[i]-i 中 等于0的元素
故可二分查找
C++ 代码1
class Solution {
public:
int getNumberSameAsIndex(vector<int>& nums) {
if(nums.empty()) return 0;
int l = 0, r = nums.size()-1;
while(l < r){
int mid = (l + r) >> 1;
if(nums[mid] - mid < 0) l = mid + 1;
else r = mid;
}
if(nums[r] != r) return -1;
return l;
}
};
C++ 代码2
class Solution {
public:
int getNumberSameAsIndex(vector<int>& nums) {
if(nums.empty()) return 0;
int l = 0, r = nums.size()-1;
while(l < r){
int mid = (l + r + 1) >> 1;
if(nums[mid] - mid > 0) r = mid - 1;
else l = mid;
}
if(nums[r] != r) return -1;
return l;
}
};