google ,uber 跪经

aangel 发表于 2016-6-10 04:52
直接设3个count,3个candidate,一次pass O(n)过不就可以了吗？
跟leetcode 的majority element II类似

这方法确实On 但是面试貌似不太好解释 为啥是对的， 感觉面试官要nlog n 的方法就可以啦。
sort 后 把数组分成8份, 看每一份头元素是否等于尾元素，如果是 binary search找到这个元素范围，看是否> n/4 ,如果不是 pass

49502292 发表于 2016-6-10 09:43
我觉得可以这么建segment tree吧  每个node 加个 range, 然后判断 target node 是不是在 source node ran ...

每个node存一个range，难道不是O（n）的space复杂度么？

Xochitl 发表于 2016-6-10 09:52
每个node存一个range，难道不是O（n）的space复杂度么？

面试官的意思可能是不用 extra space hashmap之类的，可以modify tree

ScottShao 发表于 2016-6-10 00:10
求问怎么用这个性质做啊

从根节点开始DFS树，记每个节点的开始时间和结束时间，对点A而言，如果[s_a, e_a]严格被B的[s_b, e_b]包含的话那么B是A的祖先。

这个题目应该是acm/icpc 2006杭州赛区的原题。

diyutianshi 发表于 2016-6-10 15:05
从根节点开始DFS树，记每个节点的开始时间和结束时间，对点A而言，如果[s_a, e_a]严格被B的[s_b, e_b]包 ...

说错了 - 是2005年

https://icpcarchive.ecs.baylor.e ... em&problem=1487

就这个了，随便搜了个解题报告：

http://blog.csdn.net/shifuwawa/article/details/5857439

diyutianshi 发表于 2016-6-10 15:06
说错了 - 是2005年

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8& ...

厉害！！