2018腾讯内部调岗面试试题3——找出数组中比左边大比右边的小的元素
2018腾讯内部调岗面试试题3——找出数组中比左边大比右边的小的元素
恋喵大鲤鱼
发布于 2018-08-03 10:14:29
发布于 2018-08-03 10:14:29
题目：以时间复杂度O(n)从长度为n的数组中找出同时满足下面两个条件的所有元素： （1）该元素比放在它前面的所有元素都大； （2）该元素比放在它后面的所有元素都小。
分析：面试官给的上面冗余的描述，其实一句话即可说明，即“以时间复杂度O(n)从长度为n的数组中找出所有比左边大比右边的小的元素”。一开始求出所有的右边最小数组rightMin，然后从左往右判断当前元素是否是左边最大，如果是则和其相邻的右边最小数（存放于最小数组rightMin）比较，如果小于，则找到了满足条件的元素。注意：左右两边第一个数不满足条件。
实现：
#include <iostream>
using namespace std;
void g_fPrintThePivotElements(int data[],int len)
{
//从右往左，寻找每个位置及其之后的最小数
int* rightMin = new int[len];
int r_min = data[len-1];
for (int i = len-1;i>=0;--i)
{
if(data[i]<r_min)
r_min = data[i];
rightMin[i] = r_min;
}
//从左往右，寻找比左边大且比右边小的数
int l_max = data[0];
for (int i=0;i<len-1;++i)
{
if(data[i]>l_max)
{
l_max = data[i];
if(data[i]<rightMin[i+1])
cout<<data[i]<<endl;
}
}
}
int main()
{
int dTestArray[]={1,8,6,9,10,15,12,20};
g_fPrintThePivotElements(dTestArray,sizeof(dTestArray)/sizeof(dTestArray[0]));
}输出：
9
10本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年05月29日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读