今天一道面试题,想问下大佬思路

给定一个数组,满足a[i] != a[i + 1],现在要你找到一个a[j]使得a[j - 1] < a[j] && a[j] > a[j +1]。要求logN的时间复杂度。

我想logn复杂度应该就是要去做二分的形式查找,然后想的是用中值定理的性质来看接下来找哪边,然后我就卡壳了,因为我感觉两边似乎都没有一个很好的办法去抛弃。想问下大佬的思路#面试题目#
全部评论
结贴 def findPeakElement(nums) -> int:# 默认一定有解,返回解的下标 left, right = 0, len(nums)-1 while left < right: mid = (left + right) // 2 if nums[mid] > nums[mid+1]: right = mid else: left = mid + 1 return left
点赞 回复 分享
发布于 2019-09-09 22:51
数组条件只有相邻不相等?
点赞 回复 分享
发布于 2019-09-09 22:30
leetcode162
点赞 回复 分享
发布于 2019-09-09 23:00
我感觉要考虑mid和mid-1 mid+1 left,right这四个数的大小关系决定选哪边
点赞 回复 分享
发布于 2019-09-09 22:51
二分,比较的时候需要加上对头尾的数的比较
点赞 回复 分享
发布于 2019-09-09 22:37
应该是二分吧,对于选定的mid,a[mid-1],a[mid],a[mid+1]有可能是/型,\型,^或者v,分类讨论一下lo和hi,v型考虑递归两边
点赞 回复 分享
发布于 2019-09-09 22:37
mid如果处于递增序列,那left=mid;如果处于递减序列,right=mid。这样行不
点赞 回复 分享
发布于 2019-09-09 22:34
return *max_element(nums.begin(),nums.end());
点赞 回复 分享
发布于 2019-09-09 22:32
如果j-1,j,j+1递增就是在右边,反之在左边,要不然就是找到了,递归结束。二分查找的变种
点赞 回复 分享
发布于 2019-09-09 22:31
这样的要求先递增后递减吧,之前面头条出过
点赞 回复 分享
发布于 2019-09-09 22:30

相关推荐

04-15 23:42
中山大学 Java
ResourceUtilization:过几天楼主就会捧着一堆offer来问牛友们该怎么选辣
点赞 评论 收藏
分享
牛客583549203号:腾讯还好,况且实习而已,实习生流动性很大,属于正常现象,记得和HR委婉解释
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
05-29 15:00
教授A:“你为什么要讲这么久,是要压缩我们对你的评议时间吗?你们别以为这样就能够让我们对你们少点意见。”&nbsp;“从你的发言和论文格式就能知道你的性格啊。”…….&nbsp;感觉被狠狠霸凌了。
码农索隆:“教授您好,首先我想回应您提出的两点疑问。” “关于我讲解时间较长的问题:这绝非为了压缩各位老师的评议时间。这份毕业设计是我过去几个月倾注了全部心血的作品,从构思、实验、调试到撰写,每一个环节都反复打磨。我深知时间宝贵,所以选择详细讲解,是希望能更完整、清晰地展示它的核心创新点、实现过程和验证结果,确保老师们能充分理解它的价值和我的努力。我完全理解并重视评审环节的意义,也做好了充分准备来听取各位老师的专业意见和批评。几个月的研究都坚持下来了,我怎么可能害怕老师们的点评呢?今天站在这里,正是抱着虚心学习、诚恳求教的态度而来。” “如果我的展示确实超时,影响了后续流程,烦请老师们随时示意,我会立刻调整。我非常期待并预留了充足的时间,希望能听到老师们宝贵的建议和深入的讨论。” “其次,关于您提到‘从发言和论文格式就能知道我的性格’。教授,我对此感到非常困惑和不安。学术研究和答辩的核心,难道不应该是作品本身的质量、逻辑的严谨性、数据的可靠性和结论的合理性吗?论文格式有明确的规范要求,我尽最大努力遵循了这些规范。如果格式上存在疏忽或不足,这属于技术性、规范性的问题,恳请老师们具体指出,我一定认真修改。但将格式问题或个人表达风格(如讲解时长)直接上升为对个人性格的评判,甚至以此作为质疑我学术态度和动机的依据,这让我感到非常不公平,也偏离了学术评议应有的客观和严谨原则。” “我尊重每一位评审老师的专业权威,也衷心希望能得到老师们对我的工作内容本身的专业指导和批评指正。任何基于研究本身的意见,无论多么尖锐,我都会认真聆听、反思并改进。但我恳请老师们,能将评议的焦点放在我的研究本身,而不是对我个人进行主观的推断或评价。谢谢各位老师。”
点赞 评论 收藏
分享
评论
点赞
9
分享

创作者周榜

更多
牛客网
牛客企业服务