2018腾讯内部调岗面试试题3——找出数组中比左边大比右边的小的元素

题目:以时间复杂度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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

Python循环对象 ,函数

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

9910
来自专栏机器学习实践二三事

Numpy使用3

上一篇博客介绍了numpy的几种初始化方式和numpy的数据类型(dtype)和shape的相关知识,这篇介绍numpy矩阵的索引与切片 矢量化 numpy数组...

19380
来自专栏Java爬坑系列

【JAVA零基础入门系列】Day10 Java中的数组

  什么是数组?顾名思义,就是数据的组合,把一些相同类型的数放到一组里去。   那为什么要用数组呢?比如需要统计全班同学的成绩的时候,如果给班上50个同学的成绩...

22360
来自专栏Python攻城狮

数据结构与算法 - 排序与搜索排序与搜索

冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重...

11530
来自专栏五分钟学算法

每周一算:Move Zeros

思路:创建一个临时数组nonZeroElements,遍历nums,将nums中非0元素赋值到nonZeroElements中,而后按顺序将nonZeroEle...

12020
来自专栏desperate633

Python爬虫之正则表达式入门正则表达式语法正则表达式实例ReMatch对象贪婪匹配和最小匹配

Re库是Python的标准库,主要用于字符串匹配 调用方式: import re

8610
来自专栏游戏开发那些事

【Cocos2d-x游戏开发】细数Cocos2d-x开发中那些常用的C++11知识

  自从Cocos2d-x3.0开始,Cocos2dx就正式的使用了C++11标准.C++11简洁方便的特性使程序的可拓展性和可维护性大大提高,也提高了代码的书...

11530
来自专栏贺贺的前端工程师之路

字面量,常量和变量之间的区别?

经常看到这三者,基本每天作为一个程序媛的我,都和这三者在打着交道。之前每个都会使用,但是这样的来区别三者之间的关系还是第一次。从定义到实际例子,这次全面搞清楚,...

10010
来自专栏Python中文社区

Python函数的基本特征详解

今天开始,我们来讲讲函数,简而言之一个函数就是将一些语句集合在一起的部件,它们能够不止一次的在程序中运行。函数还能计算出一个返回值,并能够改变作为函数输入的参数...

13640
来自专栏老司机的技术博客

宝宝都能学会的python编程教程6:列表(list)

上期编程题的答案如上图。 列表(list) list是一种有序的集合,可以随时添加和删除其中的元素。 当索引超出了范围时,Python会报一个IndexErr...

36860

扫码关注云+社区

领取腾讯云代金券