LeetCode面试题 08.03. 魔术索引每日一题7月31

小鱼儿 2023-03-03 11:18 4阅读 0赞

## 问题描述： ##

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/magic-index-lcci

示例1:

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

示例2:

输入：nums = [1, 1, 1]
    输出：1

提示:

nums长度在[1, 1000000]之间

## 解题思路： ##

### 暴力求解： ###

class Solution {
    public:
        int findMagicIndex(vector<int>& nums) {
            int res = -1;
            for(int i=0;i<nums.size();){
                if(nums[i]==i){
                    return i;
                }
                
            }
            return res;
        }
    };

### 优化： ###

已知数组有序，当A\[0\]=10时，那么A\[i\]!=i  当1<=i<=9。

则我可以直接将i跳跃为10。

则可以将i=max(nums\[i\],i+1);

class Solution {
    public:
        int findMagicIndex(vector<int>& nums) {
            int res = -1;
            for(int i=0;i<nums.size();){
                if(nums[i]==i){
                    return i;
                }
                i = max(nums[i],i+1);//跳跃查找
            }
            return res;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，4人围观）

还没有评论，来说两句吧...

相关阅读

相关面试—每日一题（7）

上一篇讲到了如何写面试中的代码呢？为什么不在上一篇写呢？上一篇写的太多了，你看了多了肯定就会晕死了，有一个思考的疲劳了，考虑到了这一点。呵呵！好了，开始吧，如何写出好的面试代码

ゝ一世哀愁。/ 2023年08月17日 15:50/ 0 赞/ 122 阅读

相关每日一题：Leetcode 7.整数翻转

题目描述：给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。示例 1: 输入: 123 输出: 321 示例 2: 输入: -123

傷城~/ 2023年07月06日 06:17/ 0 赞/ 24 阅读

相关 LeetCode_每日一题（8月）

目录 632.最小区间(没懂） 114.二叉树展开为链表 415.字符串相加 632.最小区间(没懂） ![在这里插入图片描述][waterma

拼搏现实的明天。/ 2023年03月04日 04:29/ 0 赞/ 29 阅读

相关面试题 08.03. 魔术索引

[面试题 08.03. 魔术索引][08.03.] 魔术索引。在数组`A[0...n-1]`中，有所谓的魔术索引，满足条件`A[i] = i`。给定一个有序整数数组，编

叁歲伎倆/ 2023年03月03日 14:26/ 0 赞/ 8 阅读

相关力扣每日练习 - 面试题 08.03 魔术索引

文章目录题目描述解题代码运行结果简要解析题目描述 > 魔术索引。在数组A\[0…n-1\]中，有

以你之姓@/ 2023年03月03日 14:23/ 0 赞/ 4 阅读

相关 LeetCode面试题 08.03. 魔术索引每日一题7月31

问题描述：魔术索引。在数组A\[0...n-1\]中，有所谓的魔术索引，满足条件A\[i\] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组

小鱼儿/ 2023年03月03日 11:18/ 0 赞/ 5 阅读

相关 LeetCode面试题29.顺时针打印矩阵每日一题6月5日

问题描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。来源：力扣（LeetCode）链接：[https://leetcode-cn.com/

「爱情、让人受尽委屈。」/ 2023年02月15日 10:25/ 0 赞/ 21 阅读

相关 LeetCode面试题64. 面试题64. 求1+2+…+n，每日一题6月2日

题目描述：求 `1+2+...+n` ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。来源：力

Dear 丶/ 2023年02月14日 10:12/ 0 赞/ 16 阅读

相关 LeetCode101,对称二叉树，，每日一题5月31

问题描述：给定一个二叉树，检查它是否是镜像对称的。来源：力扣（LeetCode）链接：[https://leetcode-cn.com/problems/sy

秒速五厘米/ 2023年02月14日 02:22/ 0 赞/ 2 阅读

相关程序员面试金典-0803-魔术索引

程序员面试金典-0803-魔术索引本题为有序数组找出下标和索引值相同的最小值，主要有两个思路： 1：有序数组，势必要分治法； 2：递归处理魔术索引。

川长思鸟来/ 2022年11月17日 14:53/ 0 赞/ 192 阅读