找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 511|回复: 0
收起左侧

[资源分享] 12: Find Magic Index

[复制链接]

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-3-2015 01:53 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

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)内完成
  1. class Solution {
  2. public:
  3.     int getMagicIndex(vector<int> &A) {
  4.         if(A.empty()) return -1;
  5.         int n = A.size();
  6.         if(A[0] > 0 || A[n-1] < n-1) return -1;
  7.         int l = -1, r = n-1;
  8.         while(l+1 < r){
  9.             int m = (l+r) >> 1;
  10.             if(A[m] >= m) r = m;
  11.             else l = m;
  12.         }
  13.         return A[r] == r ? r : -1;
  14.     }
  15. };
复制代码


您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表