[Leetcode][程序员面试金典][面试题08.03][JAVA][魔术索引][递归][优化]

缺乏、安全感 2023-03-03 12:25 9阅读 0赞

#### 【问题描述】\[简单\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 逐个查找 ######

**时间复杂度：O(N) 空间复杂度：O(1)**

public int findMagicIndex(int[] nums) { 
            for (int i = 0, length = nums.length; i < length; i++) { 
                if (i == nums[i])
                    return i;
            }
            return -1;
        }

###### 2. 逐个查找优化 ######

有序升序整数  
假如nums\[0\]=100，假如是升序的，那么num\[0\]后面的值都不会比100小，所以i如果还是一步步的加，效率肯不高，我们直接让i从100开始，因为小于100的i肯定是查找不到的。

**时间复杂度：O(N) 空间复杂度：O(1)**

public int findMagicIndex(int[] nums) { 
            for (int i = 0, length = nums.length; i < length; i++) { 
                if (i == nums[i])
                    return i;
                if (nums[i] > i + 1) { 
                    //如果nums[i]大于i+1,我们就让i加上nums[i] - 1，
                    // 这里减1的目的是为了抵消上面for循环中的i++。
                    //这里判断的时候为什么是nums[i] > i + 1而不是
                    //nums[i] > i ,因为如果num[i]只比i大1的话，
                    //直接执行上面的i++就可以了，没必要再执行下面的计算
                    i = nums[i] - 1;
                }
            }
            return -1;
        }

###### 3. 递归 ######

一想到排序数组很容易想到的是二分法查找，但是这里如果直接使用二分法查找的i不一定是最小的，有重复的数字。  
\[0,0,2,2,5\] 存在多个满足  
所以有一种方式就是先把数组劈两半，先在前面一半查，如果找到就直接返回，如果没找到就在后面部分查，并且前面部分和后面部分再分别劈两半，一直这样递归下去……。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

**时间复杂度：O(N) 空间复杂度：O(1)**  
![在这里插入图片描述][20200731141150451.png]

class Solution { 
        public int findMagicIndex(int[] nums) { 
            return getAnswer(nums, 0, nums.length - 1);
        }
    
        public int getAnswer(int[] nums, int left, int right) { 
            if (left > right) { 
                return -1;
            }
            int mid = (right - left) / 2 + left;
            int leftAnswer = getAnswer(nums, left, mid - 1);
            if (leftAnswer != -1) { 
                return leftAnswer;
            } else if (nums[mid] == mid) { 
                return mid;
            }
            return getAnswer(nums, mid + 1, right);
        }
    }

#### 【总结】 ####

##### 暴力容易想到 也容易想到二分 但没想到它是不能直接用二分，而只能用二分剪枝的思想 直接使用二分一定要单调递增或递减 #####

转载链接：https://leetcode-cn.com/problems/magic-index-lcci/solution/zhu-ge-cha-zhao-yi-ji-you-hua-di-gui-you-hua-ji-di/  
参考链接：https://leetcode-cn.com/problems/magic-index-lcci/solution/mo-zhu-suo-yin-by-leetcode-solution/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230208/9e4505374c8d473983bd917863a5db39.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20230208/fce94cda32d74131ad1bae2267bb32a2.png
[20200731141150451.png]: /images/20230208/9b023db27eda446cbcc834d6d06e5fd9.png