程序员面试金典-08.04魔术索引

Posted on | In

乍一看是一道非常简单的题目，多思考一番其实内有乾坤。

面试题 08.03. 魔术索引

魔术索引。 在数组A[0…n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

示例1:

1
2
3
4
>  输入：nums = [0, 2, 3, 4, 5]
>  输出：0
>  说明: 0下标的元素为0
>

示例2:

1
2
3
>  输入：nums = [1, 1, 1]
>  输出：1
>

提示:

  1. nums长度在[1, 1000000]之间

遍历

遍历解法能ac是因为leetcode给的数据量太小了，我想这题出的本意应该是让我们用二分查找的方法去找到魔术索引。

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

二分查找 + 分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int findMagicIndex(vector<int>& nums) {
      if (nums.empty()) return -1;
      return search(nums, 0, nums.size() - 1);
    }
    int search(vector<int>& nums, int left , int right){
        if (left >= right){
            if (nums[left] == left)   return left;
            else    return -1;
        }
        int mid = left + (right - left)/2 ;
        int ret = 0;
        if (nums[mid] == mid){                  
            //当中点是魔术索引时,还需在左半段去找是否有魔术索引,有则是更小的
            ret = search(nums, left, mid - 1);
            return ret == -1 ? mid : ret;
        } 
        else{
            // 当中点不是魔术索引时,需要左右都要查找是否有魔术索引
            // 因为是有序的当左边找到了,则右边就无需继续查找了
            ret = search(nums, left, mid - 1);
            if (ret != -1)  return ret;
            ret = search(nums, mid + 1, right);
            return ret != -1 ? ret : -1; 
        }
        return -1;
    }
};