魔术索引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

算法知识视频讲解

Java

Simms

还是利用二分法，不过过了缩小mid的范围

 public boolean findMagicIndex(int[] A, int n) {
        // write code here
        int head = 0;
        int tail = n-1;

        return check(A, head, tail);
    }

    public boolean check(int [] A , int left, int right){
        if(left > right){
            return false;
        }

        int mid = (left + right) /2;
        int start = mid ;
        int end = mid ;

        while(mid != 0 && A[mid] == A[start-1]){
            start--;
        }

        while(mid != A.length-1 && A[mid] == A[end+1]){
            end++;
        }

        if(start <= A[mid] && A[mid] <= end && start != end){
            return true;
        }

        return check(A, left, start-1) || check(A, end + 1, right);
    }

发表于 2020-07-09 16:36:58 回复(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, A[mid]) || find(A, mid + 1, hi);
        } else {
            return find(A, lo, mid - 1) || find(A, A[mid], hi);
        }
    }
}

发表于 2017-07-21 08:41:54 回复(0)

Java

风之少年/fw

    public boolean findMagicIndex(int[] A, int n) {
        for (int i = 0; i < n; ) {
            if (A[i] == i) {
                return true;
            } else {
                i = Math.max(A[i], i + 1);
            }
        }

        return false;
    }

编辑于 2016-12-09 21:44:45 回复(0)

Java

peng.tan

二分递归

import java.util.*;

public class MagicIndex {
   public static boolean findMagicIndex(int[] A, int n) {
		return twoFen(A, 0, n - 1);
	}

	public static boolean twoFen(int[] A, int begin, int end) {
		if (begin > end) {
			return false;
		}
		int mid = (begin + end + 1) / 2;
		if (A[mid] == mid) {
			return true;
		} else {
			return twoFen(A, begin, mid - 1) || twoFen(A, mid + 1, end);
		}
	}
}

发表于 2016-11-09 22:31:40 回复(0)

Java

蓝胖子SHD

	 public static boolean findMagicIndex02(int[] A, int n) {
		 int low=0;
		 int high=A.length-1;
		 while(low<high){
		
			 int mid=(low+high)>>1;
			 if(A[mid]>mid){
				 high=mid;
			 }else {
				 return true;
			 }
		 }
		 return false;
	 }

发表于 2016-08-11 11:30:32 回复(1)