|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- 魔术索引。 在数组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]之间
复制代码
- class Solution:
- def findMagicIndex(self, nums: List[int]) -> int:
- return self.helper(nums, 0, len(nums) - 1)
-
- def helper(self, nums: List[int], left: int, right: int) -> int:
- if left > right:
- return -1
- mid = int((right - left) / 2 + left)
- left_ans = self.helper(nums, left, mid - 1)
- if left_ans != -1:
- return left_ans
- elif nums[mid] == mid:
- return mid
- else:
- return self.helper(nums, mid + 1, right)
复制代码 |
|