魔术索引

问题描述:

魔术索引。 在数组A[0…n-1]中,有所谓的魔术索引,满足条件A[i] = i。给定一个有序整数数组,编写一种方法找出魔术索引,若有的话,在数组A中找出一个魔术索引,如果没有,则返回-1。若有多个魔术索引,返回索引值最小的一个。

示例1:

 输入:nums = [0, 2, 3, 4, 5]
 输出:0
 说明: 0下标的元素为0
示例2:

 输入:nums = [1, 1, 1]
 输出:1
提示:

nums长度在[1, 1000000]之间

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/magic-index-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解决方案

对于不存在重复元素的数组可以使用如下方式二分,若当前索引大于当前值,则证明魔术索引在当前索引之后,若小于当前值则证明则证明魔术索引在其之前,等于则就是魔术索引。但是该问题中存在重复元素,只有当前值等于当前索引时才能排除其后的元素,需要进行两边分治。

代码如下:

class Solution {
    public int findMagicIndex(int[] nums) {
        return binSearch(nums, 0, nums.length - 1);
    }
    public int binSearch(int[] nums, int left, int right){
        if(left == right){
            return nums[left] == left ? left : -1;
        }
        int mid = left + (right - left) / 2;
        if(nums[mid] == mid){
            return binSearch(nums, left, mid);
        }
        int pre = binSearch(nums, left, mid);
        if(pre != -1){
            return pre;
        }
        return binSearch(nums, mid + 1, right);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 线段树

    对于给定数组nums,修改nums中某个下标的值的操作记做update(index, val),获得nums某个区间元素和的操作记做query(start,en...

    你的益达
  • 搜索插入位置

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

    你的益达
  • 至少有K个重复字符的最长子串

    找到给定字符串(由小写字符组成)中的最长子串T , 要求T 中的每一字符出现次数都不少于 k 。输出 T的长度。

    你的益达
  • 程序员进阶之算法练习(三十四)LeetCode专场

    LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 1、2、3题都是Medium的难度,大概是头条的面试题水准; 4、5题是Hard...

    落影
  • Leetcode 215. Kth Largest Element in an Array

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • 剑指Offer LeetCode 面试题57. 和为s的两个数字

    输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

    TrueDei
  • LeetCode 324. Wiggle Sort II

    这道题目很有意思,有意思的是使用O(n)的时间效率和O(1)的空间效率解决。我会写一篇专业的博客来介绍一下

    ShenduCC
  • 442. Find All Duplicates in an Array

    Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appe...

    luozhiyun
  • LeetCode45. 跳跃游戏 II

     还是以样例为例,[2,3,1,1,4],起点是nums[0] = 2,那么在nums[1] = 3和nums[2] = 1中我们应该选择哪个进行跳跃?很...

    mathor
  • LeetCode 152 Maximum Product Subarray

    ShenduCC

扫码关注云+社区

领取腾讯云代金券