面试题 08.03. 魔术索引

魔术索引。 在数组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

说明:

  1. nums长度在[1, 1000000]之间
  2. 此题为原书中的 Follow-up，即数组中可能包含重复元素的版本

解题思路

二分查找

方法一

顺序遍历数组，比较每个元素的值是否和其下标相等
注意到当 面试题 08.03. 魔术索引 - 图1 时，可以让遍历的下标 面试题 08.03. 魔术索引 - 图2，略过 i 到 nums[i] 中间不可能相等的点

  1. class Solution {
  2. public:
  3.     int findMagicIndex(vector<int>& nums) {
  4.         int len = nums.size();
  5.         for(int i = 0;i < len;) {
  6.             if(nums[i] == i) {
  7.                 return i;
  8.             }else if(nums[i] > i){
  9.                 i = nums[i];
  10.             }else{
  11.                 i++;
  12.             }
  13.         }
  14.         return -1;
  15.     }
  16. };

方法二

二分查找

  1. class Solution {
  2. public:
  3.     int findMagicIndex(vector<int>& nums) {
  4.         return recBinary(nums,0,nums.size()-1);
  5.     }
  6.     //闭区间 [left,right]
  7.     int recBinary(vector<int>& nums,int left,int right) {
  8.         if(left > right)
  9.             return -1;
  10.         int mid = left + ((right - left) >> 1);
  11.         int leftAns = recBinary(nums,left,mid-1);
  12.         if(leftAns != -1) {
  13.             return leftAns;
  14.         }else if(mid == nums[mid]){
  15.             return mid;
  16.         }
  17.         return recBinary(nums,mid+1,right);
  18.     }
  19. };