81.第 1 组百度面试题
1.一个 int 数组,里面数据无任何限制,要求求出所有这样的数 a[i],其左边的数都小于等
于它,右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。
/* 81.第 1 组百度面试题 1.一个 int 数组,里面数据无任何限制,要求求出所有这样的数 a[i],其左边的数都小于等 于它,右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。 利用一个辅助数组,记录每一个元素右侧的最小值是多少 rightMin 在顺序遍历 保存当前最大值 即左边最大的 那么若两者相等 则满足 当前值大于左边所有 又是右边最小 小于右边所有 */ #include<iostream> using namespace std; #define max(a,b) a>b?a:b #define min(a,b) a<b?a:b void solve(int data[],int len) { int* rightMin=new int[len]; int left_max; //输出原数组 for(int i=0;i<len;i++) cout<<data[i]<<" "; cout<<endl; rightMin[len-1]=data[len-1]; for (int i=len-2;i>=0;i--)//从右向左 rightMin[i]=min(data[i],rightMin[i+1]); left_max=0; for (int i=0;i<len;i++) { left_max=max(data[i],left_max); if(left_max==rightMin[i]) cout<<data[i]<<":大于数组左边数,小于数组右边数"<<endl; } } int main() { int data[10]={1,3,2,4,6,7,5,9,11,10}; int data2[7] ={7,10,2,6,19,22,32}; solve(data2,7); solve(data,10); }