魔术索引II

[编程题]魔术索引II

热度指数：8279 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知一个数组A[0..n-1]和其大小n（不下降序列，元素值可能相同），判断是否存在A[i]=i，返回值为bool，要求时间复杂度小于o(n)。

测试样例：

[1,1,3,4,5]

返回：true

算法知识视频讲解

Python

华科平凡

python solution

# -*- coding:utf-8 -*-
class MagicIndex:
    def findMagicIndex(self, A, n):
        # write code here
        for i,v in enumerate(A):
            if i==v:
                return True
        return False

发表于 2017-10-01 22:34:41 回复(1)

Python

张淮

# -*- coding:utf-8 -*-
class MagicIndex:
    def findMagicIndex(self, A, n):
        # write code here
        if n==0:
            return True
        return self.magic(A,0,n-1)
    def magic(self,A,start,end):
        if start>end:
            return False
        mid=(start+end)/2
        if mid==A[mid]:
            return True
        else:
            min_v=min(mid-1,A[mid])
            max_v=max(mid+1,A[mid])
            return self.magic(A,start,min_v) or self.magic(A,max_v,end)

发表于 2017-07-11 20:12:38 回复(0)