|
亲!马上注册或者登录会查看更多内容!
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
对于sorted intarray,我们有intarray【i】-i是单调不减的,这是因为(intarray[i+1]-(i+1)) - (intarray【i】-i) = intarray[i+1]-intarray【i】-1,由于intarray[i+1]>=intarray【i】+1,所以intarray[i+1]-intarray【i】-1>=0,所以题目转换为求0在数组[intarray【i】-i]中的lower_bound,二分查找即可在O(logN)内完成
- class Solution {
- public:
- int getMagicIndex(vector<int> &A) {
- if(A.empty()) return -1;
- int n = A.size();
- if(A[0] > 0 || A[n-1] < n-1) return -1;
- int l = -1, r = n-1;
- while(l+1 < r){
- int m = (l+r) >> 1;
- if(A[m] >= m) r = m;
- else l = m;
- }
- return A[r] == r ? r : -1;
- }
- };
复制代码
|
|