[アルゴリズム]int配列a[]は、すべてのa[i]を求め、左側はそれ以下、右側はそれ以上である.
2302 ワード
のように
a[]={7,9};
しゅつりょく
7,9
例えばa[]={7,10,2,6,19,22,32}である.
出力19,22,32
アルゴリズム:
簡単で、空間で時間を変えて、各要素の右側の区間の最小値を記録して、右に移動する時に左の最大値を更新して、もし現在の要素が右の最小値以下で、左の最大値以上であれば、条件に合って、出力します.
void foo(int a[], int n)
{
if(n > 0)
{
int* rightMin = new int[n];
int min = a[n-1],i;
rightMin[n-1] = min;
for(i = n-2; i >= 0; --i)
{
if(a[i] < min )
{
min = a[i];
}
rightMin[i] = min;
}
int leftMax = a[0];
for(i = 0; i < n; ++i)
{
if(a[i] >= leftMax && a[i] <= rightMin[i+1])
{
cout<<a[i]<<" ";
}
}
delete[] rightMin;
}
}