假设我们有一棵树,其节点包含一些数字。
我需要在这棵树中找到 n 个最大的数字。
我脑子里有两个算法:
1. 使用 BFS 或 DFS 遍历树并将其节点放入数组中,然后使用快速排序对其进行排序并返回 n 个第一个元素。
此方法的时间复杂度为 O(|V| + |E| + |V|log|V|),空间复杂度为 O(|V|)
2. 其次是迭代树找到最大元素并标记它 n 次。所以时间复杂度是 O(N*(|V| + |E|)),空间复杂度也是 O(|V|)。
哪个解决方案更好,也许我走错了路,还有更好的解决方案吗?
最佳答案
还有一个标准heap选择算法不起作用?
基本算法是(假设k
是你要选择的项目数)
create an empty min-heap
for each node (depth-first search)
if heap.count < k
heap.Add(node)
else if node.Value < heap.Peek.Value()
heap.RemoveSmallest()
heap.Add(node)
for
循环完成后,您的堆将包含 k
个最大值。您可以通过以下方式按升序获取它们:
while heap.count > 0
output (heap.RemoveSmallest().Value)
如果想升序排列,就按照上面的方法从堆中取出,放到一个数组中,然后反转数组即可。
这个算法是 O(n log k),其中 n
是树中的节点数,k
是你想要的项目数。
关于在树中找到最大的 n 个节点的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27062771/