还是那个比利杨
还是考到那题popular number
我上来先写了one pass O(n)解法
然后问能不能再优化 我说用binary search
这个时候我已经准备开始写了 他问我 还能不能再优化?
我以为已经是O(logn)了。。没想到会问这个 当时我就懵逼了
其实优化的办法就是 如果你提前判断每个锚点左右两边的数是否相等 就可能可以省掉那一边的binary search
如果你提前判断几个锚点之间是否相等 如果相等那么可以直接输出结果
类似这样的 想了我二十分钟。。最后都没时间写了
果不其然第二天收到拒信
感觉被套路了 还有就是我太菜了。。