美文网首页
LeetCode 面试题 08.03. 魔术索引 | Pytho

LeetCode 面试题 08.03. 魔术索引 | Pytho

作者: 大梦三千秋 | 来源:发表于2020-07-31 21:54 被阅读0次

    面试题 08.03. 魔术索引


    题目来源:力扣(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)
    

    实现结果


    实现结果

    欢迎关注


    公众号 【书所集录

    相关文章

      网友评论

          本文标题:LeetCode 面试题 08.03. 魔术索引 | Pytho

          本文链接:https://www.haomeiwen.com/subject/xqpsrktx.html