专栏首页C/C++基础2018腾讯内部调岗面试试题3——找出数组中比左边大比右边的小的元素

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 条评论
登录 后参与评论

相关文章

  • 基数排序简介及其并行化

      基数排序号称线性时间排序算法中性能最好,速度最快的排序算法。本文将简要概括其算法思想,串行代码及其并行化。

    Dabelv
  • 左值、右值与常引用

    左值(Lvalue)是C++中的一个基本概念,指可寻址的非只读表达式。通俗来讲,凡是可以出现在赋值运算符左边的表达式都是左值。与左值相对的就是右值(Rvalue...

    Dabelv
  • 二路归并排序简介及其并行化

    归并排序是分治法(Divide and Conquer)的一个典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若...

    Dabelv
  • 剑指Offer面试题:32.数字在排序数组中出现的次数

      既然输入的数组是排序的,那么我们很自然地就能想到用二分查找算法。在题目给出的例子中,我们可以先用二分查找算法找到一个3。由于3可能出现多次,因此我们找到的3...

    Edison Zhou
  • 自己动手写数据结构之封装动态数组

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    suveng
  • 4.C++中的函数重载,C++调用C代码,new/delete关键字,namespace(命名空间)

    可以看到输出结果,每个函数的入口地址都不一样(重载函数的入口地址,必须使用强制转换来获取)

    张诺谦
  • codeforces 315 B.Sereja and Array

    Sereja has got an array, consisting of n integers, a1, a2, ..., an. Sereja i...

    xindoo
  • 如何在Ubuntu 16.04使用Buildbot建立持续集成系统

    Buildbot是一个基于Python的持续集成系统,用于自动化软件构建,测试和发布过程。

    angel_郁
  • 归并排序

    归并排序是典型的分而治之策略的应用。主要是把一个数组分成若干个子数组进行从小到大的归并直至有序。下面所说的归并排序默认为2路归并排序。

    AI那点小事
  • 洛谷P3384 【模板】树链剖分

    题目描述 如题,已知一棵包含N个结点的树(连通且无环),每个节点上包含一个数值,需要支持以下操作: 操作1: 格式: 1 x y z 表示将树从x到y结点最短路...

    attack

扫码关注云+社区

领取腾讯云代金券