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

给定一个数组,满足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

相关推荐

2025-12-12 19:01
南京航空航天大学 C++
秋招没咋投,准备&nbsp;wxg&nbsp;转正之后摆烂了。结果不堪字节&nbsp;HR&nbsp;的骚扰还是面了一下字节。之前想去字节的时候怎么面都挂。现在想着随便面一下结果三面技术面都意外顺利还有加面。十月中旬字节发了意向,wxg&nbsp;转正结果无响应。十月底字节拉了保温群,wxg&nbsp;口头通过,系统显示考核中。十一月初和字节&nbsp;ld&nbsp;交流之后得知&nbsp;base&nbsp;居然能选海外,甚至能小&nbsp;wlb&nbsp;一下,wxg&nbsp;无响应无人联系。十一月中旬把字节&nbsp;base&nbsp;转到了海外,wxg&nbsp;流程灰了,一问超时忘处理了,过两天又变考核中了。十一月下旬字节换了海外&nbsp;HR&nbsp;对接,问了期望薪资,wxg&nbsp;考核终于显示通过,无&nbsp;HR&nbsp;保温,无其他保温。十一月底给字节报了个天价,想吓吓他们,同时告诉微信字节要开了,微信无响应。同样十一月底字节&nbsp;HR&nbsp;告诉我确实给不到那么高,但是能拿期权补上,问能不能接受。微信无响应。同样十一月底字节&nbsp;HR&nbsp;告知了具体方案,符合预期。&nbsp;微信无响应。十二月上旬催&nbsp;wxg&nbsp;不开我就盲拒了,wxg&nbsp;HR&nbsp;火急火燎的打电话问情况,问期望。我给了一个不算夸张的总包数字,因为今年市场在涨,过了三天还不联系我,我再催,约时间下午打电话,非得在我给出的数字上压下去几万,微信又不差这点,为什么不能满足我,让我没有拒绝的理由呢?一番纠结抗争,求稳还是追求挑战,最终选择接受迎接新的挑战,因为堂吉诃德永远不会停下脚步!回想起来,在&nbsp;wxg&nbsp;谈薪的阶段,我认为并没有给予我一定的重视,即使&nbsp;HR&nbsp;表示我在实习期间的表现和之前的面评都很靠前。也没有感觉到想要争取我,虽然我表示拒了&nbsp;offer&nbsp;之后要给我加面委定&nbsp;t6&nbsp;再涨,但我三个月没面试让我面面委那就是白给,还是算了。有缘再见了我亲爱的&nbsp;wxg,再见了曾经的梦中情厂,再见亲爱的&nbsp;mt,再见亲爱的朋友们。也再见,北京的一切。我想润了。秋招结束,卸载牛客,下一个三年,下一个五年,下一个十年后再来看看。
面试中的大熊猫爱吃薯...:我嫉妒得狗眼通红
点赞 评论 收藏
分享
评论
点赞
9
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务