作者:僵小鱼 | 来源:互联网 | 2023-07-09 18:14
【问题描述】[简单]
【解答思路】
1. 逐个查找
时间复杂度:O(N) 空间复杂度:O(1)
public int findMagicIndex(int[] nums) {for (int i &#61; 0, length &#61; nums.length; i < length; i&#43;&#43;) {if (i &#61;&#61; nums[i])return i;}return -1;}
2. 逐个查找优化
有序升序整数
假如nums[0]&#61;100&#xff0c;假如是升序的&#xff0c;那么num[0]后面的值都不会比100小&#xff0c;所以i如果还是一步步的加&#xff0c;效率肯不高&#xff0c;我们直接让i从100开始&#xff0c;因为小于100的i肯定是查找不到的。
时间复杂度&#xff1a;O(N) 空间复杂度&#xff1a;O(1)
public int findMagicIndex(int[] nums) {for (int i &#61; 0, length &#61; nums.length; i < length; i&#43;&#43;) {if (i &#61;&#61; nums[i])return i;if (nums[i] > i &#43; 1) {i &#61; nums[i] - 1;}}return -1;}
3. 递归
一想到排序数组很容易想到的是二分法查找&#xff0c;但是这里如果直接使用二分法查找的i不一定是最小的&#xff0c;有重复的数字。
[0,0,2,2,5] 存在多个满足
所以有一种方式就是先把数组劈两半&#xff0c;先在前面一半查&#xff0c;如果找到就直接返回&#xff0c;如果没找到就在后面部分查&#xff0c;并且前面部分和后面部分再分别劈两半&#xff0c;一直这样递归下去……。
时间复杂度&#xff1a;O(N) 空间复杂度&#xff1a;O(1)
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 &#61; (right - left) / 2 &#43; left;int leftAnswer &#61; getAnswer(nums, left, mid - 1);if (leftAnswer !&#61; -1) {return leftAnswer;} else if (nums[mid] &#61;&#61; mid) {return mid;}return getAnswer(nums, mid &#43; 1, right);}
}
【总结】
暴力容易想到 也容易想到二分 但没想到它是不能直接用二分&#xff0c;而只能用二分剪枝的思想 直接使用二分一定要单调递增或递减
转载链接&#xff1a;https://leetcode-cn.com/problems/magic-index-lcci/solution/zhu-ge-cha-zhao-yi-ji-you-hua-di-gui-you-hua-ji-di/
参考链接&#xff1a;https://leetcode-cn.com/problems/magic-index-lcci/solution/mo-zhu-suo-yin-by-leetcode-solution/