微软电面

say543 发表于 2017-12-15 15:30
那因该是 (i+1 < j) 固定有三个element 做个binary search吧?

请问可以说的详细点么

jingjingfly 发表于 2017-12-20 08:38
已发送 字数

楼主回复速度超快呢！万分感谢！

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

先binary search找到peak点 然后分别对左半部和右半部做一次binary search即可

hychin 发表于 2017-12-20 16:36
先binary search找到peak点 然后分别对左半部和右半部做一次binary search即可

这是O(3lgn)的，不行哈

say543 发表于 2017-12-20 15:41
at least 三个点 可以确定increasing or decreasing (除了peak) 每次check middle 是否meet if not mee ...

如果在纸上画一下是不行的哈，两边都要判断，无法选一边

实在想不到不能klogn的logn，请问楼主当时怎么说的？

jingjingfly 发表于 2017-12-15 17:17
嗯？能具体说下你的这个解法吗？

我当时在面试官的提示下用divide & conquer做的

能分享下怎么divide and conquer 吗 .... LZ

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies