魔术索引

发表于
本文字数： 806 阅读时长 ≈ 1 分钟

LeetCode每日一题，面试题08.03. Magic Index LCCI

先看题目描述

大意就是给定一个 nums 数组，找到其中使 nums[i] = i 的最小索引，若没有，就返回 -1

算法和思路

暴力法

暴力法很好理解，就直接遍历，找到的第一个 nums[i] = i 的下标就直接返回，若遍历完后没找到满足条件的下标，就返回 -1

优化后的暴力法

因为题目中提到给的 nums 数组是有序的，于是可以利用这点来优化暴力法，例如在遍历时遍历到 nums[2] = 100，因为 nums 数组有序，nums[2] 之后的数肯定都大于等于 100，因此下一个下标就直接从 100 开始遍历，这样就可以对暴力法进行优化

算法源码

暴力法

1
2
3
4
5
6
7
8
class Solution {
    public int findMagicIndex(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (i == nums[i]) return i;
        }
        return -1;
    }
}

优化后的暴力法

1
2
3
4
5
6
7
8
9
class Solution {
    public int findMagicIndex(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (i == nums[i]) return i;
            if (i < nums[i]) i = nums[i] - 1;
        }
        return -1;
    }
}