Edu*_*yan 1 c++ algorithm vector time-complexity binary-search-tree
一旦我接受"一家知名公司"的采访,面试官就让我找到了BST的中位数.
int median(treeNode* root)
{
}
我开始实施我提出的第一个蛮力解决方案.我将所有数据填充到std::vector<int>带有inorder遍历(以使所有内容在向量中排序)并获得中间元素.因此,我的算法是O(N),用于插入向量中的每个元素,并使用O(1),+ O(N)的内存查询中间元素.那么做同样的事情是否有更有效的方式(在内存或复杂性方面).
提前致谢.
它可以通过有序遍历在O(n)时间和O(logN)空间上完成,当你到达n/2第一个节点时停止,只需携带一个计数器,告诉你已经遍历了多少个节点 - 不需要实际填充任何向量.
如果你可以将你的树修改为rank-tree(每个节点也有关于子树中节点数量的信息,那么它是你的根) - 你可以在O(logN)时间内轻松解决它,只需向n方向移动/ 2个元素.
| 归档时间： |
|
| 查看次数： |
3159 次 |
| 最近记录： |