首页 > 试题广场 >

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

算法知识视频讲解

王六六

这才是标准答案，虽然最坏情况是O（n）。

class MagicIndex:
    def findMagicIndex(self, A, n):
        # write code here
        i=0#初始下标
        while i<n:
            if A[i]<i:#因为下标大于值，所以递增下标，使得值增大
                i+=1
            elif A[i]>i:#如果下标小于值，那么实际上有：
                        #下标i到下标A[i-1]的位置都不可能存在A[i]=i
                        #因为下标i对应的A[i]已经大于A[i-1]了                i=A[i]
            else:
                return True
        return False

对于第二种情况举个例子：

[-3,4,4,4,5,5,8,9]

一、i=0,值小于i，i递增，i=1

二、因为A【i】==4，可以看出i=2,3都是不可能的，所以直接i=4

三、A【i】==5，i=4，依然i=5

四、发现符合条件，return

编辑于 2019-06-27 09:35:20 回复(0)

更多回答

九城城主

应该是从i：0~n - 1进行遍历，如果当前A[i] == i，返回true；如果A[i] < i，则i ++；如果A[i] > i，则令i = A[i]，即跳过A[i] - i个元素（因为序列是非递减的，所以A[i] > i时，至少到i = A[i]处，才有可能出现A[i] == i）。

例如2， 2， 2， 4， 5序列，i == 0时，A[i] = 2，则应跳过i = 1，直接比较i = 2处。

代码如下所示：

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

编辑于 2016-08-13 13:12:30 回复(8)

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)

松华皮蛋me

#include <iostream>
#include <vector>
using namespace std;
class MagicIndex {
public:
    bool findMagicIndex(vector<int> A, int n,int start=0,int end =0) {
        // write code here
        /*
        事实上，看到A[5]=3时按照二分查找的做法，我们需要递归搜索右半部分。不过，如搜索左半部分，
        我们可以跳过一些元素，值递归搜索A[0]到A[3]的元素。A[3]是第一个可能成为魔术索引的元素。
        综上：我们得到一种搜索模式，先比较midIndex和midValue是否相同。
        然后，若两者不同，则按如下方式递归搜索左半部分和右半部分。

        左半部分：搜索索引从start到min(midIndex-1,midValue)的元素。

        右半部分：搜索索引从max(midIndex+1,minValue)到end的元素。
        */
        if (start > end || start < 0 || end > n)
        {
            return false;
        }
        int mid = (end - start) / 2 + start;
        if (A[mid] == mid)
        {
            return true;
        } 
        else 
        {
            int leftEnd = min(mid - 1, A[mid]);
            int rightStart = max(mid + 1, A[mid]);
            return findMagicIndex(A, n, start, leftEnd) || findMagicIndex(A, n, rightStart, end);
        }
    }
};

发表于 2016-04-30 16:14:00 回复(7)

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)

Alex-大伟

public class MagicIndex {

	/**
	 * @param args
	 */
	

	public boolean findMagicIndex(int[] A, int n) {
		if (n == 0) {
			return true;
		}
		int count = 0;
		while (count < n) {
			if (A[count] == count) {
				return true;
			} else if (A[count] < count) {
				count++;
			} else {
				count = A[count];
			}
		}
		return false;
	}
	// 方法2：二分查找
	public boolean findMagicIndex1(int[] A, int n){
		return findMagic(A, 0, n - 1);
	}
	
	public static boolean findMagic(int[] A, int low, int high) {
		if (low > high) { // 说明没有找到魔术索引，返回false
			return false;
		}
		int mid = (low + high + 1) / 2;
		if (A[mid] == mid) {
			return true;
		}
		// 两边序列都有可能有魔术索引
		else {
			return findMagic(A, low, mid - 1) || findMagic(A, mid + 1, high);
		}
	}
}

发表于 2016-10-09 11:29:02 回复(1)

C/C++

Ga_li_dun_farming_guy

// 跟第一题一样的答案。没有差别，也是只用找左子树就好了

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

发表于 2018-12-26 17:11:43 回复(4)

Aurora1

    public boolean findMagicIndex(int[] A, int n) {
        return exist(A, 0, n - 1);
    }

    boolean exist(int[] A, int i, int j) {
        if (i > j)
            return false;
        int m;
        do {
            m = (i + j) >> 1;
            if (A[m] > m) {
                if (exist(A, A[m], j)) { //因为两边都可能存在魔术索引，所以都要搜，下同
                    return true;
                }
                j = m - 1;
            } else if (A[m] < m) {
                if (exist(A, i, A[m])) {
                    return true;
                }
                i = m + 1;
            } else {
                return true;
            }
        } while (i <= j);

        return false;
    }

编辑于 2016-08-28 16:54:54 回复(0)

将鹰

与魔术索引I一样，下面代码没有二分法，没有递归，但复杂度低于O（n）
bool findMagicIndex(vector<int> A, int n) {
        // write code here
        bool flag = false;
    int temp = 0;
    while (temp < n)
    {
        if (A[temp] == temp)
        {
            flag = true;
            break;
        }
        else
        {
            temp = (temp > A[temp]) ? temp + 1 : A[temp];
        }
    }
    return flag;
    }

发表于 2017-02-17 21:01:34 回复(0)

C/C++

玖玖

思路：二分法递归

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

        int llow = low + 1;
        int lhigh = mid - 1;
        int ln = lhigh - llow + 1;
        bool lresult = myFindMagicIndex(llow, lhigh, A, ln);
        if(lresult)
            return true;
        
        int rlow = mid + 1;
        int rhigh = high - 1;
        int rn = rhigh - rlow + 1;
        bool rresult = myFindMagicIndex(rlow, rhigh, A, rn);
        if(rresult)
            return true;
        
        return false;
    }
};

发表于 2016-09-06 16:06:10 回复(1)

C/C++

kakaan

直接顺序查找，但是不符合小于O(n)的题意的

    bool findMagicIndex(vector<int> A, int n) {
        for(int i=0;i<n;i++)
            if(A[i] == i)
            	return true;
        return false;
    }

发表于 2016-09-02 16:07:14 回复(2)

python开发工程师

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

// write code here

int idx=0;

int data=A[idx];

while(data<n)

{

//参考剑指Offer 里面一种交换策略，最坏O(n)，两个魔术索引都AC了

if(data==idx)

return true;

int tmp=A[data];

if(tmp==data)

return true;

A[data]=data;

data=tmp;

}

return false;

}

发表于 2016-08-08 19:51:42 回复(0)

C/C++

Pis

算法：二分查找是肯定能查到的，因为是有序数组。但是因为有重复，mid>A[mid]情况下不好说是向左走还是向右走，但是肯定两种方向有一个是对的。 class MagicIndex {
public: bool half_find(vector<int> a,int start,int end){ while (start<=end){ int mid = start +(end - start)/2;  if(mid == a[mid]) return true;  else if(mid > a[mid])
                start = mid + 1;  else  end = mid - 1;  } return false;  } bool half_find_r(vector<int> a,int start,int end){ while (start<=end){ int mid = start +(end - start)/2;  if(mid == a[mid]) return true;  else if(mid > a[mid])
                end = mid - 1;  else  start = mid + 1;  } return false;  } bool findMagicIndex(vector<int> A, int n) { // write code here  int start = 0;  int end = n - 1;  return half_find(A,start,end)||half_find_r(A,start,end);  }
};

发表于 2016-08-07 17:47:48 回复(1)

Ron

	public boolean findMagicIndex(int[] A, int n) {
		// write code here
		/*
		 * 由于A是递增数组，可递归使用二分法，看是否满足魔术索引的条件
		 * 如果当前中间值满足，则返回true，如果不满足
		 * 由于序列非递减，两边序列都有可能有魔术索引
		 * 
		 */
		if(A == null || A.length != n || n <= 0){
			return false;
		}
		return findMagic(A, 0, n-1);
	}

	private boolean findMagic(int[] A, int begin, int end) {
		// TODO Auto-generated method stub
		System.out.println("["+begin+","+end+"]");
		if(begin > end){//说明此部分序列没有找到魔术索引，可以返回false
			return false;
		}
		int index = (begin+end+1)/2;
		if(A[index] == index){
			return true;
		}
		return findMagic(A, begin, index-1)||findMagic(A, index+1, end);
	}

发表于 2016-05-20 11:29:06 回复(0)

Hahaha1993

class MagicIndex {
public:
    bool findMagicIndex(vector<int> A, int n) {
        // write code here
        if(n==0)
            return true;
        else
            return magic(A,0,n-1);
        
    }
    
    bool magic(vector<int> A,int start,int end){
        if(start>end)return false;
        int mid=(start+end)/2;
        if(A[mid]==mid)
            return true;
        //此时魔术索引可能在左边也有可能在右边 也有可能同时出现在左右边
        return magic(A,start,min(mid-1,A[mid]))||magic(A,max(A[mid],mid+1),end);
         
    }
};

发表于 2016-04-06 16:20:29 回复(2)

牛妹夫

import java.util.*;

public class MagicIndex {
    public boolean findMagicIndex(int[] A, int n) {
        // write code here
        int low = 0;
        int high = n-1;
        while(low <= high){
            int mid = (low + high)/2;
            if(A[mid] == mid)
                return true;
            if(A[mid] > mid){ 
            	if(mid+1<n && A[mid+1] >mid + 1) high= mid - 1;
            	if(mid+1<n && A[mid+1] ==mid+1) return true;
                if(mid+1<n && A[mid+1] <mid + 1) low = mid + 1;
            }
			if(A[mid] < mid){
            	if(mid+1<n && A[mid+1] ==mid+1) return true;
            	if(mid+1<n && A[mid+1] >mid+1) low = mid + 1;
                if(mid+1<n && A[mid+1] <mid+1) high = mid - 1;
            }
        }
        return false;
    }
}

发表于 2016-02-03 12:03:50 回复(1)

lytofd

因为考虑可能有连续相同元素，故不可使用类似于二分的方法去寻找，只能使用类似快排的递归方式去寻找，然后把结果进行相或，找到一个元素符合就可以判定为真。

bool fun(vector <int >A,int left,int right)

{

int mid;

if(left>right)

return false;

if(left==right)

{

if(A[left]==left)

return true;

else

return false;

}

mid=(left+right)/2;

return (fun(A,left,mid-1))||(fun(A,mid+1,right));

}

bool findMagicIndex(vector<int> A, int n) {

// write code here

return fun(A,0,A.size()-1);

}

编辑于 2015-09-01 20:22:16 回复(1)

actor6

class MagicIndex {
public:
void magic(vector<int> &A, int low, int high, bool &flag)
{
if(low <= high)
{
int mid = (low + high) / 2;
if(A[mid] == mid){
flag = true;
return;
}
else{
magic(A, low, mid-1, flag);
magic(A, mid+1, high, flag);
}
}
}
bool findMagicIndex(vector<int> A, int n) {
// write code here
int low = 0, high = n-1;
bool flag = false;
magic(A, low, high, flag);
return flag;
}
};

发表于 2020-12-17 20:41:40 回复(0)

GG2020

# -*- coding:utf-8 -*-
class MagicIndex:
    def findMagicIndex(self, A, n):
        if len(A) == 0 : return False
        mid = n>>1
        if A[mid] ==  mid or A[0] == 0 or A[n-1] == n-1 : return True
        elif A[mid] > mid: return self.findMagicIndex(A[:mid], mid)
        else: return self.findMagicIndex(A[mid:], mid)

编辑于 2020-10-20 21:13:55 回复(1)

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)

C/C++

字节内推小跟班

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

发表于 2020-04-29 13:22:19 回复(0)