こっちはいいんだけどね…。
https://leetcode.com/contest/weekly-contest-142/problems/find-in-mountain-array/
問題
ある数列があり、その数列は山を成している。
すなわち、あるところまで真に単調増加で、その後真に単調減少となる。
この数列の具体的な中身は不明だが、最大で100個まで値を取得できるものとする。
値がTであるindexが存在するならそれを求めよ。
解法
まず最大値を特定しよう。
これは区間の三分探索で絞り込める。
区間の両端と、間2か所の計4か所の値を求めれば、そのうちの最大値の位置によって区間を2/3に絞れる。
最大値が特定できれば、単調増加の区間と単調減少の区間それぞれで二分探索するだけ。
int A[101010]; class Solution { public: int get(int v,MountainArray &M) { if(A[v]==-1) A[v]=M.get(v); return A[v]; } int findInMountainArray(int target, MountainArray &M) { MINUS(A); int N=M.length(); int L=0,R=N-1; while(R-L>=6) { int m1=(2*L+R)/3; int m2=(L+2*R)/3; int V[4]={ get(L,M), get(m1,M), get(m2,M), get(R,M), }; if(V[0]==V[1]) R=m1; else if(V[0]==V[2]) R=m2; else if(V[1]==V[2]) L=m1,R=m2; else if(V[1]==V[3]) L=m1; else if(V[2]==V[3]) L=m2; else { int x=max_element(V,V+4)-V; if(x==0) R=m1; if(x==1) R=m2; if(x==2) L=m1; if(x==3) L=m2; } } int i; int id=L; for(i=L;i<=R;i++) { get(i,M); if(A[i]>A[id]) id=i; } if(A[0]<=target&&target<=A[id]) { int i; int cur=-1; for(i=20;i>=0;i--) if(cur+(1<<i)<=id && get(cur+(1<<i),M)<=target) cur+=1<<i; if(cur>=0 && get(cur,M)==target) return cur; } if(target<=A[id]&&target>=get(N-1,M)) { int i; int cur=id; for(i=20;i>=0;i--) if(cur+(1<<i)<N && get(cur+(1<<i),M)>=target) cur+=1<<i; if(get(cur,M)==target) return cur; } return -1; } };
まとめ
interactive面倒だなと思って後回しにしたらあとがもっと面倒だった。