首页 > 试题广场 >

魔术索引I

[编程题]魔术索引I

热度指数：10648 时间限制：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

算法知识视频讲解

codermanFans

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

return getMagic(A,0,n - 1);

}

public boolean getMagic(int[] A, int left,int right) {

if(left <= right){

int middle = (left + right) / 2;

if (A[middle] == middle) {

return true;

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

return getMagic(A, 0 ,middle - 1);

} else if(A[middle] < middle){

return getMagic(A, middle + 1 ,right);

}

return false;

}

递归版的二分搜索。。。

发表于 2015-09-03 16:16:20 回复(0)

更多回答

datong

题目要求由于O(n)，考虑采用二分法单边，时间复杂度O(logn)。

class MagicIndex {
private:
    bool magic(vector<int> A,int start, int end){
        if(start >= end) return false;
        int mid = (start+end)/2;
        if(mid == A[mid]) return true;
        else if(mid > A[mid]) return magic(A,mid+1,end);
        else return magic(A,start,mid);
    }
public:
    bool findMagicIndex(vector<int> A, int n) {
        if(n == 0) return true;
        else return magic(A,0,n);
    }
};

加个非递归版本的：

class MagicIndex {
public:
    bool findMagicIndex(vector<int> A, int n) {
        if(n == 0) return true;
        int mid = 0,start = 0,end = n;
        while(start < end){
            mid = (start+end)/2;
            if(mid == A[mid]) return true;
            else if(mid > A[mid]) start = mid + 1;
            else end = mid ;
        }
        return false;
    }
};

编辑于 2015-09-14 15:30:39 回复(13)

C/C++

kakaan

题目的特征：

1、升序数组

2、由于O(n)

所以顺序查找肯定不行，那么对于这个有序的序列，那就是二分查找

    bool findMagicIndex(vector<int> A, int n) {
        int l=0,r=n-1,mid = 0;
        while(l<=r)
        {
            mid = (l+r)/2;
            if(A[mid]==mid) 
                return true;
            else if(A[mid]<mid) 
                l=mid+1;
            else 
                r=mid-1;
        }
        return false;
    }

发表于 2016-09-02 15:59:57 回复(0)

null167

来个最简单的：

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

return A[0]==0;

}

数组升序排列，因为数组数字各不相同，并且都是整数，每次最少加1，如果第一个都不是，那对应数组每个地方的值肯定比索引大

发表于 2017-05-24 15:39:17 回复(6)

Aurora1

public boolean findMagicIndex(int[] A, int n) {
        int i = 0, j = n - 1, m;
        do {
            m = (i + j) >> 1;
            if (A[m] > m) {
                j = m - 1;
            } else if (A[m] < m) {
                i = m + 1;
            } else {
                return true;
            }
        } while (i <= j);

        return false;
    }

编辑于 2016-08-25 20:27:20 回复(0)

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:33:48 回复(1)

MichaelTim

class MagicIndex {
public:
    bool findMagicIndex(vector<int> A, int n) {
        return DFS(A, 0, n-1);
    }
    bool DFS(vector<int> &A, int low, int high){
        if(low == high) return A[low] == low;
        if(A[low] == low || A[high] == high) return true;
        if(A[low] > low || A[high] < high) return false;
        else return DFS(A, low, (low+high)/2) || DFS(A,(low+high)/2+1,high);
    }
};

发表于 2016-10-12 20:51:34 回复(0)

C++

勇敢牛牛，不怕困难！

class MagicIndex {
public:
  bool findMagicIndex(vector<int> A, int n) {
    int l = 0, r = n - 1;
    while (l <= r) {
      int m = l + ((r - l) >> 1);
      if (A[m] == m) return true;
      if (A[m] > m) r = m - 1;
      else l = m + 1;
    }
    return false;
  }
};

发表于 2021-08-05 14:58:06 回复(0)

南少201911241210480

class MagicIndex {
public:
    bool findMagicIndex(vector<int> A, int n) {
        // write code here
        int i=0;
        while(A[i]<i&&i<n)
        {
            i++;
        }
        return A[i]==i;
        
    }
};

负数也可以检验，这应该是完整版，就算有负数，找到A[i]不小于i的地方，比较A[i]和i的大小，如果相等就是魔术索引，如果A[i]>i,那肯定不是了，因为以后A[i]不可能等于i了

发表于 2020-03-05 21:43:17 回复(0)

屁颠屁颠地、

class MagicIndex {
public:
bool findMagicIndex(vector<int> A, int n) {
// write code here
if(A[0]==0)
return true;
else
return false;
}

};

这道题漏洞明显，根据他的限制条件直接可以破解。

正常思路肯定就是通过二分法去解。

首先题目给的是升序并且必须是整数，所以当任意A[i] > i, 那么大于i的右边部分全部不成立，可以全部放弃掉。而由于升序，并且不重复的条件A[i] < i不可能出现，不用考虑。

所以要写的话，代码编写思路就是二分法，头尾相加除以二，得到mid。

当A[mid] == mid,返回true。

当A[mid] > mid,后面部分全部可以去掉，然后从头到mid在进行二分查找。

而A[mid] < mid不可能会出现不考虑。

这样就解完了。

这题坑爹的地方就是他给的限制太多了，连脑子都不用动，因为限制又要升序，又不能重复，又必须是整数所以你直接判断第一项就足够了，如果第一项是A[0] == 0，那么就是魔法的条件，输出true就可以了后面的不用管了；如果第一项A[0] ！= 0，那么后面的由于又要升序又要不重复，就不可能存在A[i] == i，即序列位置等于序列值得现象，直接输出false就OK。

编辑于 2018-12-15 15:30:59 回复(1)

边境牧羊犬

//假设数组严格升序，题目中又说了每个数都不同，那么这道题不就简单了吗。。。O(1)

class MagicIndex {
public:
    bool findMagicIndex(vector<int> A, int n) {
        // write code here
        if(A[0]==0)
            return true;
        else
            return false;
    }
};

发表于 2018-07-05 16:35:06 回复(2)

C/C++

hyh_ustc

思路

升序数组，因此如果A[i] > i, 则任何 j>i,A[j]=j都不可能成立，同理如果A[i] < i, 则任何 j < i, A[j]=j 都不可能成立。

二分查找

如果A[mid] == mid,返回true
如果A[mid] > mid,则后半部分不可能有解
如果A[mid] < mid，则前半部分不可能有解

代码

class MagicIndex {
public:
    bool findMagicIndex(vector A, int n) {
        // write code here
        int mid = 0, left = 0, right = n-1;

        while(left <= right) {
            mid = (left + right) / 2;
            if(A[mid] == mid)
                return true;

            if(A[mid] < mid){
                left = mid+1;
            } else {
                right = mid-1;
            }
        }

        return false;
    }
};

发表于 2018-06-25 17:24:49 回复(0)

小Andy

class MagicIndex {
public:
    bool findMagicIndex(vector<int> A, int n) {
        // 如果A[i]<i，则它后面的值都会满足A[i] < i
        // 因为A[i]是升序数组，元素值各不相同,i也是升序，但i每次只增1（int值里面最小的增量）
        int start = 0;
        int end = n - 1;
        int mid;
        while (start <= end)
        {
            mid = (start + end) / 2;
            if (A[mid] == mid)
                return true;
            else if (A[mid] > mid)
                end = mid - 1;
            else
                start = mid + 1;
        }
        return false;
    }
};

编辑于 2017-11-17 11:01:59 回复(0)

想风一样自由

//二分法，　先找中间，　大于mid ，那肯定在左边；小于mid ，就在右边 
bool findMagicIndex(vector<int> A, int n) {
        // write code here
        int i=0, j=n-1;
        while(i<j){
            int mid = (j-i)/2;
            if(A[mid] == mid)
                return true;
            else if(A[mid] > mid)
                j = (j-i)/2;
            else if(A[mid] < mid)
                i = (j-i)/2;
        }
        return false;
    }

发表于 2017-09-16 17:41:07 回复(0)

C/C++

Salmon-William

思路：题目是**吗，这和动态规划和递归有什么关系吗？就是存在A[i]==i,
就返回true的一个问题，第二个方法优化一些，但是建议使用第一种方法，因为
第一种方法的代码就是下面一题的答案，直接遍历一遍，省得麻烦
class MagicIndex {
public:
    bool findMagicIndex(vector<int> A, int n) {
        for(int i=0;i<n;i++)
            {
            if(A[i]==i)
                return true;
        }
        return false;
    }
};
优化了一下算法，如果A[i]!=i,下一个i直接跳到A[i],会少一些复杂度
class MagicIndex {
public:
    bool findMagicIndex(vector<int> A, int n) {
        for(int i=0;i<n;i++)
            {
            if(A[i]==i)
                return true;
            else
                i=A[i]-1;
        }
        return false;
    }
};

编辑于 2017-09-13 16:45:17 回复(1)

C/C++

蓝魔4

递归的代码！
class MagicIndex {
public:
    bool Magic(vector<int> &A,int index,int n)
    {
        if(index==n)
            return false;
        if(A[index]==index)
            return true;
        return Magic(A,index+1,n);
    }
    bool findMagicIndex(vector<int> A, int n) {
        int index=0;
        return Magic(A,0,n);
    }
};

发表于 2017-09-08 10:02:40 回复(0)

InGodWeTrust

真搞笑，我写个错误的程序居然通过了，无语！

import java.util.*;

public class MagicIndex {
    public boolean findMagicIndex(int[] A, int n) {
        if(A==null||n==0)	return false;
        int start=0;
        int end=0;
        while(start<=end){
            int mid=(start+end)/2;
            if(mid<A[mid]){
                start=mid+1;
            }else if(mid>A[mid]){
                end=mid-1;
            }else{
                return true;
            }
        }
        return false;
    }
}

发表于 2017-08-12 09:14:00 回复(0)

阿狸不是猫

import java.util.*;
/*
思路：因为是一个升序数组，所以可以考虑二分法
*/
public class MagicIndex {
    public boolean findMagicIndex(int[] A, int n) {
        int start =0;
        int end =n-1;

        while(start<=end){
            int mid =(start+end)/2;
            if(A[mid]>mid){
                end =mid-1;
            }else if(A[mid]==mid) return true;
            else{
                start=mid+1;
            }
        }
        return false;
    }
}
运行时间：92ms
占用内存：11180k

发表于 2017-06-29 17:29:07 回复(0)

SXJ君子

  public boolean findMagicIndex(int[] A, int n) {
       boolean flag = false;
		 for(int i = 0 ; i < n;i++){
			 if(A[i] == i){	 
				 return true;
			 }else if(A[i] > i){
				 return  false;
			 }else{
                 flag = false;
             }
		 }
		return flag;      
    }

发表于 2016-12-07 18:21:19 回复(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)

天山二侠

class MagicIndex {
public:
    bool findMagicIndex(vector<int> A, int n) {
        // write code here
        if(A.front() >= n || A.back() < 0)
            return false;
    
        int l = 0, r = A.size() - 1;
        int mid;
        while(l < r)
        {
            mid = (l + r) / 2;
            if(A[mid] < mid)
                l = mid + 1;
            else if(A[mid] == mid)
                return true;
            else
                r = mid - 1;
        }
        return A[l] == l;
    }
};

发表于 2016-08-21 17:18:41 回复(3)