题目描述

假设一个单调递增的数组里的每个元素都是整数并且是唯一的。

请编程实现一个函数找出数组中任意一个数值等于其下标的元素。

例如，在数组[-3, -1, 1, 3, 5]中，数字3和它的下标相等。

样例

输入：[-3, -1, 1, 3, 5]

输出：3

算法1

(二分)

1. 如果最后二分出来的r满足条件，则return r
2. 如果最后二分出来的结果还是不满足条件，则说明不存在，返回-1

时间复杂度

$O(logn)$

C++ 代码

class Solution {
public:
    int getNumberSameAsIndex(vector<int>& A) {
        int l = 0, r = A.size() - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(A[mid] - mid >= 0) r = mid;
            else l = mid + 1;
        }

        if(A[r] - r == 0) return r;
        return -1;
    }
};

算法2

(暴力枚举)

时间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    int getNumberSameAsIndex(vector<int>& nums) {
        int i = 0;
        for(i = 0; i < nums.size(); i ++)
            if(i == nums[i])
                return i;

        if(i != nums[i]) i = -1;
        return i;
    }
};