现在的位置: 首页 > 综合 > 正文

81 第1 组百度面试题 数组 左边的数都小于等 于它,右边的数都大于等于它

2018年05月02日 ⁄ 综合 ⁄ 共 805字 ⁄ 字号 评论关闭

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);  
} 

抱歉!评论已关闭.