最左原位

作者: IT_Matters | 来源:发表于2016-07-07 17:07 被阅读36次

有一个有序数组arr,其中不含有重复元素,请找到满足arr[i]==i条件的最左的位置。如果所有位置上的数都不满足条件,返回-1。
给定有序数组arr及它的大小n,请返回所求值。

测试样例:
[-1,0,2,3],4
返回:2

思路

不含重复元素的有序数组,可以看成严格递增的序列. 看到有序,自然而然想到二分查找.这里我们对题目进行一些简化,便于理清思路.
数组的下标是严格增加1,可以看成一条斜率为1的直线,而数组是严格递增的, 每次增长至少为1.此处为了方便大家理解,将其简化为一条斜率>1的直线,实际上应该是折线,可能与y=x有多个交点.如下图所示.


示意图

如果arr[mid]<mid,交点如果存在只能在其右侧,将搜索范围变成[mid+1,hi]
同理如果arr[mid]>mid,交点如果存在只能在其左侧,将搜索范围变成[lo,mid-1]
如果arr[mid]=mid,记录下当前位置,继续向左寻找下一个交点.搜索范围是[lo,mid-1].

完整代码如下:

 public int findPos(int[] arr, int n) {
        int lo=0,hi=n-1;;
        int pos=-1;
        int mid=0;

        if(arr[0]>=n||arr[n-1]<0)return pos;

        while(lo<=hi){
           mid=lo+(hi-lo)/2;           
           if(arr[mid]>mid)hi=mid-1;
           else if(arr[mid]<mid) lo=mid+1;
           else{
               pos=mid;
               hi=mid-1;
           }                      
       }
        return pos;
    }

相关文章

  • 最左原位

    有一个有序数组arr,其中不含有重复元素,请找到满足arr[i]==i条件的最左的位置。如果所有位置上的数都不满足...

  • 二分查找(2)

    最左原位 原位指的是arr[m]==m的位置。找出一个有序单调不减数组中最左原位,若无返回-1. 思路: 对于有序...

  • 6_6最左原位

    有一个有序数组arr,其中不含有重复元素,请找到满足arr[i]==i条件的最左的位置。如果所有位置上的数都不满足...

  • 原位测试、原位试验和原位检测的概念

    【《铁路工程基本术语标准》GB/T50262-2013】 第3.7.1条:原位测试(in-situ test或IS...

  • 钢结构中大跨度空间的施工技术应用

    大跨度钢结构常用的几种施工方法 一、高空原位单元安装法 高空原位单元安装法 高空原位安装法包括高空原位散装法和高空...

  • 回归原位

    一年了,一年前的今天猝不及防,忐忑不安,坐立不安,希望那顿饭赶紧过去。 如果没有那顿饭多好,起码这...

  • 回归原位

    初二一早三娘的儿子就回来了,要接三娘三爷去青岛,姐姐们也就不用回来了。三娘家四个闺女一个儿子,都在青岛黄岛。 几个...

  • 原位癌

    没想到,昨天那个电话,真的是因为我情况不好,才给我打的。 今天早上我想起来,给那个APP里面冲了48,和医生说了4...

  • 不守原位

    如果知道一个地方很好,并且有资格永远待下去,可是,偏偏不守原位,离弃的这个好地方,这就是犯罪。 当然,这样的犯...

  • AI快捷键 PC版

    原位粘贴技巧 CTRL+C 复制 CTRL+F 原位贴到前面 CTRL+B 原位贴到后面 页面切换技巧 在开多个A...

网友评论

    本文标题:最左原位

    本文链接:https://www.haomeiwen.com/subject/ekeljttx.html