0%

leetcode每日一题-魔术索引

Posted on In ,

魔术索引

image1

方法一：暴力搜索

遍历一遍数组，如果$nums[i]=i$就返回，否则返回-1。

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

复杂度分析：

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(1)$。

方法二：二分查找

由于存在重复元素，因此不能简单的二分查找。我们先将数组一分为二，先查找左半部分，如果左半部分有满足条件的，就返回索引。如果没有，就看$nums[mid]$是否等于$mid$，如果等于，就返回$mid$，否则就去右半部分查找，过程和上面的一样，因此可以用递归来实现。

1
class Solution {
2
    public int findMagicIndex(int[] nums) {
3
        return getAnswer(nums, 0, nums.length-1);
4
    }
5
6
    public int getAnswer(int[] nums, int left, int right){
7
        int mid = left + (right-left)/2;
8
        if(left > right){
9
            return -1;
10
        }
11
        int leftAnswer = getAnswer(nums, left, mid-1);
12
        if(leftAnswer != -1){
13
            return leftAnswer;
14
        }else if(mid == nums[mid]){
15
            return mid;
16
        }
17
        return getAnswer(nums, mid+1, right);
18
    }
19
}

复杂度分析：

  • 时间复杂度：$O(n)$，最坏情况下会达到$O(n)$。
  • 空间复杂度：$O(n)$，最坏情况下递归n层。