[アルゴリズム]配列内の中枢要素を探し出す
2152 ワード
任意のipivot,a[i]>=a[pivot],a[i]>=a[pivot]に対して1つの追加の配列と少量の空間しか使用できないように,整数配列を与えた.
構想
1、一つの配列tを用いて記録し、t[i]はa[0]~a[i]の最大値を記録する
2、aの末尾の首から遍歴し、minを用いてa[i]~a[n-1]の最小値を記録し、min>=t[i]であれば、iが中枢元素であるインデックスを表す
本明細書は、知識共有署名-非商業的使用3.0ライセンス契約に基づいて許可される.転载、演繹を歓迎して、しかし本文の署名林が舞い上がるを保留しなければならなくて、もしコンサルティングが必要ならば、手紙を出してください。
構想
1、一つの配列tを用いて記録し、t[i]はa[0]~a[i]の最大値を記録する
int *t = new int[n];
for(int i = 0, max = ~0; i < n; ++i){
if(a[i] > max){
max = a[i];
}
t[i] = max;
}2、aの末尾の首から遍歴し、minを用いてa[i]~a[n-1]の最小値を記録し、min>=t[i]であれば、iが中枢元素であるインデックスを表す
int pivot =-1;
for(int i = n-1, min = 0x7fffffff; i >= 0; --i){
if(a[i] < min){
min = a[i];
}
if(min >= t[i]){
pivot = i;
break;
}
}
delete[] t;本明細書は、知識共有署名-非商業的使用3.0ライセンス契約に基づいて許可される.転载、演繹を歓迎して、しかし本文の署名林が舞い上がるを保留しなければならなくて、もしコンサルティングが必要ならば、手紙を出してください。