首页 > 试题广场 >

魔术索引I

[编程题]魔术索引I
  • 热度指数:10509 时间限制: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
题目要求由于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)
题目的特征:
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)
来个最简单的:
public boolean findMagicIndex(int[] A, int n) {
return A[0]==0;
}
数组升序排列,因为数组数字各不相同,并且都是整数,每次最少加1,如果第一个都不是,那对应数组每个地方的值肯定比索引大

发表于 2017-05-24 15:39:17 回复(6)
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 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)
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)
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)
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)

思路

升序数组,因此如果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)
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)
思路:题目是**吗,这和动态规划和递归有什么关系吗?就是存在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)
递归的代码!
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)
真搞笑,我写个错误的程序居然通过了,无语!
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)
  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)
比较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)