学习
实践
活动
专区
工具
TVP
写文章
专栏首页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
本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://blog.csdn.net/K346K346复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • Java岗大厂面试百日冲刺 - 日积月累,每日三题【Day23】—— 算法1

      本栏目Java开发岗高频面试题主要出自以下各技术栈:Java基础知识、集合容器、并发编程、JVM、Spring全家桶、MyBatis等ORMapping框架...

    陈哈哈
  • 查找第k小的元素(O(n)递归解法)

    今天分享一个小技巧,虽然是小技巧但是还是很有价值的,曾经是微软的面试题。题目是这样的,一个无序的数组让你找出第k小的元素,我当时看到这道题的时候也像很多人一样都...

    Angel_Kitty
  • 新手程序员靠刷题真的能进大厂吗?

    给定一个整数数组,编写一个函数,找出索引 m 和 n ,只要将索引区间 [m,n] 的元素排好序,整个数组就是有序的。(默认是递增有序数组)

    五分钟学算法
  • 【每日算法Day 88】超越妹妹教你如何做这道排序题

    给定一个整数数组,编写一个函数,找出索引 m 和 n,只要将索引区间 [m, n] 的元素排好序,整个数组就是有序的。注意:n-m 尽量最小,也就是说,找出符合...

    godweiyang
  • 剑指offer | 面试题32:最小的k个数

    题目描述 :输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

    千羽
  • 《剑指 offer》刷题记录之:查找和排序

    查找和排序都是在程序设计中经常用到的算法。常用的查找算法包括「顺序」查找、「二分」查找、「哈希表」查找和「二叉排序树」查找。本节将主要聚焦在二分查找方法,其应用...

    口仆
  • 美团面试:请手写一个快排,被我怼了!

    其实,快排说简单嘛,估计很多人也手写不出来,说难吗也有很多人你能现场手写几种方式。

    田维常
  • 腾讯课堂 IMWeb 七天前端求职提升营 Day 1

    本次的系列博文主要是针对 腾讯课堂七天前端求职提升营 课程中,所推送的面试题目及编程练习的一次汇总,期间还包括三次直播课的分享,均由腾讯导师给大家讲解,该系列博...

    Nian糕
  • 跟着节奏来,下一个算法大师就是你,此文不容错过

    其实这个问题就是一个非常经典的快排问题,但是大多数人遇到这个问题时,总是被前面的数量级总认为这样的问题无法通过排序算法完成。问题的表现形式常常用以下方式描述: ...

    CC老师
  • Android技能树 — 排序算法基础小结

    现在安卓面试,对于算法的问题也越来越多了,要求也越来越多,特别是排序,基本必考题,而且还动不动就要手写,所以陆续要写算法的文章,也正好当自己学习。o(╥﹏╥)o

    青蛙要fly
  • 二分查找算法学习总结

      这里是一个数组,数组里面都是些不重复的数字, 那我现在想要数组里面有没有74这个数字,当然了,我们用肉眼很容易判断最后一个就是74这个数字,一下就可以找到了...

    一切总会归于平淡
  • 面试某公司碰到的笔试题

    第一题,比较简单,相信通过代码可以很快的理解,思路很重要,我的思路是这样的,使用while循环遍历,每次拿到左边为0的数与右边起第一个非0数进行交换,直到左边遍...

    jiankang666
  • 最全的BAT大厂面试题整理

    版权声明:本文为博主原创文章,未经博主允许不得转载。https://www.jianshu.com/p/c70989bd5f29

    AWeiLoveAndroid
  • 剑指offer | 面试题6:重建二叉树

    前序遍历性质:节点按照 [ 根节点 | 左子树 | 右子树 ] 排序。中序遍历性质:节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。

    千羽
  • 最新字节跳动面试题与岗位层级,绩效考核制度介绍

    3.算法题三: 给一数组,让你找一对满足i<j<k && a[i]<a[j]<a[k] 的i和j和k (O(N)时间复杂度 O(N)空间复杂度)

    一个会写诗的程序员
  • 求职 | 刷题这件小事儿

    公司一般会使用“赛码”或者“牛客网”平台进行考试,不过像阿里、浪潮、中兴是有自己的考试系统。

    用户3946442
  • 快速排序的相关算法题(java)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

    程序员徐公
  • 漫画:知乎面试题(旋转数组最小值Ⅱ - 进阶版)

    今天是小浩算法“365刷题计划”第72天。继续为大家讲解二分法系列篇 - 旋转排序数组最小值Ⅱ(进阶版)。话不多说,直接看题:

    程序员小浩

作者介绍

Dabelv

腾讯后台开发工程师

腾讯 · 后台开发工程师 (已认证)

专栏

精选专题

活动推荐

关注

腾讯云开发者公众号
10元无门槛代金券
洞察腾讯核心技术
剖析业界实践案例
腾讯云开发者公众号二维码

扫码关注腾讯云开发者

领取腾讯云代金券