Cinte's Leetcode Record
0%

面试题 08.03. 魔术索引

Posted on Edited on In Disqus:
Symbols count in article: 797 Reading time ≈ 1 mins.

面试题 08.03. 魔术索引

easy的我都做不出了

稍加优化的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findMagicIndex(vector<int>& nums) {
        for(int i = 0; i < nums.size(); ++i)
        {
            if(nums[i] == i)
                return i;
            if(nums[i] > i) // 重要，利用了递增序列的性质
                i = nums[i] - 1; // 如果nums[i] > i，最好的情况是i后面直到正确答案都等于nums[i],这时候跳转过去就是正确答案，但是如果后面存在严格递增的子串，则正确答案一定再nums[i]位置后面
        }
        return -1;
    }
};
伪二分的DQ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findMagicIndex(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }
private:
    int helper(vector<int>& nums, int lo, int hi)
    {
        if(lo > hi)
            return -1;
        int mid = lo + (hi - lo) / 2;
        int left = helper(nums, lo, mid - 1);
        int right;
        if(nums[mid] == mid) // 如果中间的为mid，由于需要求最左，所以右边区间可以直接不算了
            right = mid;
        else
            right = helper(nums, mid + 1, hi);
        if(left == -1)
            return right;
        else
            return left;
    }
};