美文网首页剑指offer的java实现-数据结构与算法
剑指offer第二版-53.3.数组中数值和下标相等的元素

剑指offer第二版-53.3.数组中数值和下标相等的元素

作者: ryderchan | 来源:发表于2017-09-05 12:02 被阅读26次

    本系列导航:剑指offer(第二版)java实现导航帖

    面试题53.3:数组中数值和下标相等的元素

    题目要求:
    假设一个单调递增的数组里的每个元素都是整数且是唯一的。编写一个程序,找出数组中任意一个数值等于其下标的元素。例如,输入{-3,-1,1,3,5},输出3。

    解题思路:
    很基本的二分查找。。。

    package chapter6;
    
    /**
     * Created with IntelliJ IDEA
     * Author: ryder
     * Date  : 2017/8/15
     * Time  : 17:24
     * Description:数组中数值和下标相等的元素
     **/
    public class P267_IntegerIdenticalToIndex {
        public static int getNumberSameAsIndex(int[] data){
            if(data==null ||data.length==0)
                return -1;
            int left = 0,right = data.length-1;
            if(data[left]>0||data[right]<0)
                return -1;
            int mid;
            while (left<=right){
                mid = left+((right-left)>>1);
                if(data[mid]==mid)
                    return mid;
                else if(data[mid]<mid)
                    left = mid+1;
                else
                    right = mid-1;
            }
            return -1;
        }
        public static void main(String[] args){
            System.out.println(getNumberSameAsIndex(new int[]{-3,-1,1,3,5})); //3
            System.out.println(getNumberSameAsIndex(new int[]{0,1,2,3,4}));   //0~4
            System.out.println(getNumberSameAsIndex(new int[]{4,5,6,7,8}));   //-1
        }
    }
    
    

    运行结果

    3
    2
    -1
    

    相关文章

      网友评论

        本文标题:剑指offer第二版-53.3.数组中数值和下标相等的元素

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