我要招人

去企业版

首页 > 试题广场 >

魔术索引I

[编程题]魔术索引I

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

已知数组A[0..n-1]和数组大小n（升序数组，元素值各不相同），若存在A[i]=i则称该数组有魔术索引，请判断该数组是否存在魔术索引，返回值为bool，要求复杂度优于o(n)。

测试样例：

[1,2,3,4,5]

返回：false

算法知识视频讲解

Java

wanbf

import java.util.*;

public class MagicIndex {
    public boolean findMagicIndex(int[] A, int n) {
        // write code here
        if(A==null || A.length==0) return false;
        return findMagicIndex(0,n-1,A);
    }
    static boolean findMagicIndex(int i,int j,int[]A){
        if(A[i]==i || A[j]==j) return true;
        if(i<j){
            if(A[i]>i || A[j]<i) return false;
            int h=i+(j-i)/2;
            return findMagicIndex(i,h,A) || findMagicIndex(h,j,A);
        }
        return false;
    }
}

发表于 2022-01-15 09:46:38 回复(0)

Java

JayYeChou

二分法解决，题目没问题

public boolean findMagicIndex(int[] A, int n) {
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (A[mid] == mid) {
                return true;
            } else if (A[mid] > mid) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return false;
    }

发表于 2020-03-14 11:48:08 回复(0)

Java

面什么过什么

// 也是非常简单的二分查找了，一遍过
import java.util.*;

public class MagicIndex {
    public boolean findMagicIndex(int[] A, int n) {
        // write code here
        return find(A, 0, n - 1);
    }
    
    private boolean find(int[] a, int lo, int hi) {
        if (lo > hi) {
            return false;
        }
        int mid = (lo + hi) / 2;
        if (a[mid] == mid) {
            return true;
        } else if (a[mid] > mid) {
            return find(a, lo, mid - 1);
        } else {
            return find(a, mid + 1, hi);
        }
    }
}

发表于 2017-07-20 11:17:23 回复(0)

Java

linklist

比较index和A[index]

相等就返回true。
index小于A[index]那直接index变为A[index]，因为小于A[index]的索引的值不可能小于A[index]，只有A[index]的索引才有可能
index大于A[index],index++

public boolean findMagicIndex(int[] A, int n) {

// write code here

int index = 0;

while (index < n) {

if (A[index] < index) {

index++;

} else if (A[index] > index) {

index = A[index];

} else {

return true;

}

return false;

}

发表于 2016-09-21 13:05:12 回复(0)

Java

古月reacher

//此题题目表述已经很明确，升序数组，所以只需判断A[0]是否为0即可，不为0，后面肯定也不会存在A[i]=i的情况。

import java.util.*;

public class MagicIndex {

public boolean findMagicIndex(int[] A, int n)

{

if(A[0]==0)

return true;

else

return false;

}

发表于 2016-09-07 11:00:47 回复(3)

Java

蓝胖子SHD

	public boolean findMagicIndex(int[] A, int n) {
		int low=0;
		int high=A.length-1;
		while(low<high){
			int mid=(low+high)/2;//二分查找法
			if(A[mid]==mid){
				return true;
			}else if(A[mid]>mid){
				high=mid;
			}else{
				return false;
			}
		}
		return false;
	}

编辑于 2016-08-11 11:17:36 回复(0)