程序员面试金典 - 面试题 08.03. 魔术索引

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

魔术索引。 在数组 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]之间
• 此题为原书中的 Follow-up，即数组中可能包含重复元素的版本

题目思考

1. 如何利用数组有序这一特点?

解决方案

思路

• 这道题的输入数组有序, 乍一看可以利用二分查找来解决, 但实际并非如此
• 假设我们采用二分查找的思路, 先找到中点 m, 但实际上无论其值小于 m 或者大于 m, 都无法确定接下来应该往哪个区间遍历, 例如下面的两个例子:
  1. [0,1,3,4,5], 中点 m=2, 值为 3, 魔术索引在左侧区间(索引 1)
  2. [1,2,3,3,3], 中点 m=2, 值为 3, 魔术索引在右侧区间(索引 3)
• 接下来我们换个思路, 直接从头开始遍历下标 i, 分析各种情况:
  1. nums[i] == i: 直接返回 i, 因为我们是从小到大遍历的, i 一定是索引值最小的魔术索引
  2. nums[i] < i: 不能保证任何结论, i 只能加 1
  3. nums[i] > i: 由于数组有序, 所以下标位于[i, nums[i]-1]区间的元素值一定都大于等于 nums[i], 一定不可能是魔术索引, 所以我们可以直接将 i 赋值为 nums[i], 跳转到 nums[i] 下标继续遍历
• 如果遍历结束时仍没有发现魔术索引, 则返回 -1

复杂度

• 时间复杂度 O(N): 通过跳转我们可以提高一些效率, 但最差情况下仍需遍历整个数组(当所有下标都大于其值时)
• 空间复杂度 O(1): 只使用了几个常数空间的变量

代码

Python 3

class Solution:
    def findMagicIndex(self, nums: List[int]) -> int:
        # 从左向右遍历+比较下标与值的大小+值更大时跳转
        i = 0
        while i < len(nums):
            if nums[i] == i:
                return i
            elif nums[i] < i:
                i += 1
            else:
                i = nums[i]
        return -1

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊