题目描述
假设一个单调递增的数组里的每个元素都是整数并且是唯一的。
请编程实现一个函数找出数组中任意一个数值等于其下标的元素。
例如，在数组 [−3,−1,1,3,5] 中，数字 3 和它的下标相等。
样例
输入：[-3, -1, 1, 3, 5]
输出：3
注意：如果不存在，则返回-1。
算法1
(二分排序) )
- 由于该序列是单调的，要找到下标和元素值相等的元素，即nums[i] == i
- 可以发现如果取该序列的中点，一定有一边存在下标等于值的元素，一边不存在下标等于值的元素，即满足二段性，可以用二分
- 每次取中点，判断中点值和下标的大小关系来确定是左区间还是右区间
-
如果最后取到的值不等于自己的下标，则认为不存在，返回 -1 即可
数组二分.jpg
C++ 代码
class Solution {
public:
int getNumberSameAsIndex(vector<int>& nums) {
if( nums.empty() ) return -1;
int l = 0, r = nums.size() - 1;
//两个可能会重复
while( l <= r )
{
int mid = l + r >> 1;
if(nums[mid] == mid ) return mid;
//说明中间值可能在 右边
else if( nums[mid] < mid) l = mid + 1;
else r = mid - 1;
}
return -1;
}
};
算法2
(暴力枚举) )
因为数组是单调递增的，所以从前到后一次遍历，如果找到就返回，找不到就返回-1。
C++ 代码
class Solution {
public:
int getNumberSameAsIndex(vector<int>& nums) {
//数组判空
if(nums.empty() ) return -1;
int n= nums.size();
for(int i = 0; i < n; i++)
{
if(nums[i] == i) return i;
}
return -1;
}
};
