citadel店面

就一道题
find element in unsorted a

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

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

utput [3,5,8,10]

monotonous stack来解？

find element in unsorted array that can be found by binary search
--> for each element, try binary search, see if it works (n*log(n))
    --> for binary search to work, a number needs to be in an eligible range of binary search (left < x && x <right)
          --> for each number, for each boundary (there is log(n) of them), check if it's valid based on the boundary
                --> e.g. any number in second half < 8 would be ineligible

但是好像大体上还是 n*log(n)，想不到什么更好的办法

onerhao 发表于 2019-11-20 21:58
只要找到，左边的比自己小，右边的比自己大，这样的数就好了吧
这样的话，可以直接两边扫，也可以用range q ...

不对，仔细一想。左边比他小，右边比他大是充分不必要条件。这道题还是要divide conquer来做。保持一个min值，一个max值，不断更新。最终数字在range里就是Ok，不在range里就是不行。

楼主请问这题怎么做呀

是不是把所有out of order找出来，再去掉就行了？有什么element out of order还能被找到的吗？

只要找到，左边的比自己小，右边的比自己大，这样的数就好了吧
这样的话，可以直接两边扫，也可以用range query查

astrania 发表于 2019-11-20 20:44
monotonous stack来解？

我觉得你说的对，只要左边的都比他小，右边的都比他大，就是可以被bs找到。

感觉例子有问题, 正确的output应该是[3,10]

流星无痕 发表于 2019-12-11 04:39
不对，仔细一想。左边比他小，右边比他大是充分不必要条件。这道题还是要divide conquer来做。保持一个mi ...

也不充分吧。我能想到的是最简单的暴力O（nlogn），更简单的可能不能单独check每个元素应该有什么巧妙的算法