发个十月初的狗家面经

最后一题复杂度是O(N^4logN)？交点个数是O(N^2)，遍历交点对就是O(N^4)，然后检查的时候在intervals中检查是否存在一条线段是O(logn)？

其实感觉更优解是扫描线？

枚举两个X值，维护出覆盖这个X范围的所有水平线段(sort by Y)，同时已知X1, X2两边的垂直线段列表(sort by Y)，然后就可以在Y轴上跑扫描线了: X1轴上的垂直interval进入/离开事件; X2轴上的垂直interval进入/离开事件; 水平线段的Y进入/离开事件：维护一个<=当前Y，且和左右两边Y=curY的垂直线段都相接的水平线段Y哈希表，每次加入的时候就+= find(curY + deltaX) + find(curY - deltaX)，最后/=2。这个应该是O(N^3)的？

htfy96 发表于 2019-1-3 16:05
最后一题复杂度是O(N^4logN)？交点个数是O(N^2)，遍历交点对就是O(N^4)，然后检查的时候在intervals中检查 ...

假设有M条线，求出所有的交点的时间O(M^2)。
假设得到N个交点，遍历所有的交点对的时间O(N^2)。
M和N二者并没有直接的关系。
我的前三步都是预处理，其实不影响整体的时间复杂度。（当然，第三步用的确实是扫描线法）
所以，真正的时间复杂度大概是O(N^2*4logK), K是平均每个X/Y刻度对应的interval的个数。

wisdompeak2 发表于 2019-1-3 16:16
假设有M条线，求出所有的交点的时间O(M^2)。
假设得到N个交点，遍历所有的交点对的时间O(N^2)。
M和N二 ...

worst case (网格) N就是O(M^2)吧

Mark一下 谢谢楼主！

我有点好奇第二轮的第二题。我第一反应是O(logn)，但是试着证了一下觉得不好证。然后搜了一下发现居然是1982年的一篇PaperThe average height of binary trees and other simple trees，而且结论居然是O(sqrt(n))。

是我理解错你题目的意思了么？

P.S. 如果说是BST的average height的话，我知道算法导论上有证明average heights是O(logn)，但是第一这个证明也不容易（要先定义exponential heights这一条感觉就不容易想到，除非见过证明），第二这不等价于任意N个节点组成的二叉树高度的期望，因为分布不一样。

tsl665 发表于 2019-1-4 10:09
我有点好奇第二轮的第二题。我第一反应是O(logn)，但是试着证了一下觉得不好证。然后搜了一下发现居然是198 ...

不需要证明或计算，写出递归关系，让计算机去跑就行了。

wisdompeak2 发表于 2019-1-4 10:25
不需要证明或计算，写出递归关系，让计算机去跑就行了。

噗，是这个意思。。你说没写代码我以为是证明题。。

另外最后一题感觉可以用线段树做

htfy96 发表于 2019-1-3 16:20
worst case (网格) N就是O(M^2)吧

两种方法时间复杂度在一般情况下，其实不太好直接比较。
不过你的想法挺有意思，是可行的，效率应该也很高。

恭喜楼主

请问 第三轮里提到的“字符串转换，超高频面经”是哪一道呢？谢谢！