谷歌 店面面经

nico_sensei 发表于 2019-10-10 05:36
先找层L (0, 1, ...)，然后得到该层的元素个数M = 2^L，然后二分N并查询检验。
找层O(log N)，二分元素个 ...

大概明白了 谢谢你！
今天没米了明天加给你！

MiniMinyi 发表于 2019-10-10 05:51
假如有序的话，不用知道这一层所有节点啊。假如你知道了是第10层，这一层一共有512个点，你就用二分，首先 ...

懂了！谢谢！
明天给你加米~

楼主可以看一下这个帖子里面介绍的二分解法，也是谷歌家的

https://www.1point3acres.com/bbs/thread-554551-1-1.html

Vyronas 发表于 2019/10/10 03:43:33
可是如果还是要从root出发 worst case 应该还是O(n)呀？

不同层的那些节点就不用比较值了。也就是少那么一点点。。。

如果是排好序的 找到哪一层之后对当前层做binary search runtime O(log(n) ^2) 具体implementation可以参考LC儿儿儿 也是对binary tree做binary search？
但如果不是排好序的只能O(n)了

digdig 发表于 2019-10-10 05:07
比如找99，已知在第4层

那么从1开始，找右子树的第4层最小值（从右孩子还是一直往左走2层）80，99>80 ...

其实楼主不对O(d^2) = O(log ^2 n) != O(2logn) 只有logn^2 = 2logn

PPPPCH 发表于 2019/10/20 11:46:51
其实楼主不对O(d^2) = O(log ^2 n) != O(2logn) 只有logn^2 = 2logn

嗯嗯 是log的平方 漏写啦