关于leetcode:LeetCode-面试题-0803-魔术索引-Python

6次阅读

共计 2236 个字符，预计需要花费 6 分钟才能阅读完成。

题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/magic-index-lcci

魔术索引。在数组 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，即数组中可能蕴含反复元素的版本

思路：剪枝，分治

这里先提一下，只是看本题的话，可能会有些争议，前面再解释。

当初先审题，理清其中的关键点：

给定的数组是有序的（题目中只说有序，并未说是升序还是降序，这里联合示例，先默认是升序）；
题目要求的魔术索引，即是满足条件 A[i] = i；
数组中可能存在多个魔术索引，存在时，返回索引值最小的；
不存在魔术索引，则返回 -1。

当初，联合下面列举的关键点，能够发现数组有序（后面说了先默认升序），即便存在多个魔术索引，返回的也是最小索引的一个。那么当初能间接想到的就是间接遍历数组，当满足条件 nums[i]==i，间接返回即可，没有就返回 -1。相干代码大抵如下：

class Solution:
    def findMagicIndex(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            if nums[i] == i:
                return nums[i]
        return -1

就后面开篇说的争议，略微吐槽下，当写完下面段代码时，总感觉事件没那么简略。前面去翻阅了官网题解下的评论，确实有很大的争议。

这里大抵说下，只看本题的话，最直观的就是间接遍历，暴力法解决。能够回顾下题目，题目最初的阐明中提及到【此题为原书中的 Follow-up，即数组中可能蕴含反复元素的版本】。

这里说的是此题是可能存在反复元素的版本，所以笔者也去翻阅了原题。查阅的后果是，原题是有两局部：

一个是给定数组升序，元素值各不相同，要求给定的数组中是否存在魔术索引；
另一个是给定不降落序列，元素值可能雷同，求是否存在魔术索引。（也就是本题）

而且题目中阐明：思考是否存在一个复杂度优于 O(n) 的办法。

那么就当初就查阅的材料联合本题，进行开展阐明。

这里，在原题第一局部的根底上，从新来看这题。题目中阐明，【有可能存在多个魔术索引，元素可能反复】。那咱们将状况离开探讨：

首先先探讨，当只有一个魔术索引时。

咱们先假如存在魔术索引 i，那么也就意味着 [0, i-1] 这个区间中，索引对应的值均小于索引值，而 [i+1, n-1] 这个区间的索引对应的值则均大于索引值。咱们举个例子来阐明，例如给定如下数组：

nums = [-1, 0, 1, 3, 5]

那么，下面数组中每个索引对应的元素值与索引的差值如下：

[-1, -1, -1, 0, 1]

能够看到，下面的数组是具备枯燥性的，那么咱们只有应用二分查找，找到 0 所在的地位，返回答案即可。

再看可能存在多个魔术索引的状况，这里也同样将可能反复的状况引入进来。

假如存在这样的一个数组

nums = [0, 0, 1, 1, 4, 6]

还是依照后面的策略，用元素值减去元素对应的索引，得：

[0, -1, -1, -2, 0, 1]

当初，咱们能够看到，后果并不具备枯燥性，在这里不可能间接用二分查找的办法去解决。在这里，咱们要进行适当的剪枝，具体的做法如下：

同样还是先取两头元素，如果两头元素刚好是魔术索引，这个时候要留神，因为有可能有多个魔术索引，以后的魔术索引并不是最小的那个。然而咱们能够确定的是，两头元素右侧的索引值较大，即便存在魔术索引也不是更小的那个，那么此时能够抛开右侧局部，转而去查找左侧局部是否还有更小的魔术索引。
如果两头元素不是魔术索引，这里无奈确定魔术索引可能存在于哪侧。这个时候，两边都要进行搜寻。

在这里，根据上述的做法，咱们用递归的办法去搜寻。

具体代码实现如下（含正文）。

再啰嗦一句，其实到最初，应用递归的办法，也是往左侧找答案，反而有可能影响效率。不过，这也是一种办法，当然也能够不查究原题如何，间接一次遍历查找答案。

class Solution:
    def findMagicIndex(self, nums: List[int]) -> int:
        return self.find_magic_index(nums, 0, len(nums) - 1)

    def find_magic_index(self, nums, left, right):
        # 未找到的符合要求的返回 -1
        if left > right:
            return -1

        # 取两头元素
        mid = left + (right - left) // 2

        # 先看是否能找到第一个魔术索引，先往左侧找
        left_ans = self.find_magic_index(nums, left, mid-1)

        # 如果左侧存在，那么返回 left_ans
        if left_ans != -1:
            return left_ans
        # 如果不存在，先比拟 nums[mid] == mid
        elif nums[mid] == mid:
            return mid
        # 不存在，且 nums[mid] != mid 时，往右侧寻找
        return self.find_magic_index(nums, mid + 1, right)

公众号【书所集录】

正文完