已知数组A[0..n-1]和数组大小n(升序数组,元素值各不相同),若存在A[i]=i则称该数组有魔术索引,请判断该数组是否存在魔术索引,返回值为bool,要求复杂度优于o(n)。
测试样例:
[1,2,3,4,5]
返回:false
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; } };
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); } };
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; } };
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了
升序数组,因此如果A[i] > i, 则任何 j>i,A[j]=j都不可能成立,同理如果A[i] < i, 则任何 j < i, A[j]=j 都不可能成立。
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;
}
};
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; } };
//二分法, 先找中间, 大于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; }
思路:题目是**吗,这和动态规划和递归有什么关系吗?就是存在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; } };
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; } }
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
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; } };