算法-查找数组中第k个后继元素

Question

我无法解决一个问题，能请你帮忙吗？

For i=1 to i=n/2, if A[i]<=A[2i] and A[i]<=A[2i+1] A is called as a "bst" 

在一个有n个元素的二叉搜索树中，查找第k小的元素的时间复杂度是多少？

- Enes Erciyes

---

你确定它不应该是A[i]<=A[2i+1] and A[i]<=A[2i+2]吗？如果是这样，那么这就是一个二叉堆，你可以在O(k)的时间复杂度内找到第k小的元素。 - amit

我所写的正是它所要求的。 - Enes Erciyes

这是你的作业吗？（反问句） - ale64bit

这是2013年土耳其计算机奥林匹克竞赛的一个问题。 - Enes Erciyes

阿米特，你如何在O(k)时间复杂度内找到它？答案是O(k)。 - Enes Erciyes

请编辑此问题，将"bst"更改为"heap"，并删除您的第二个问题。@amit：您的条件是相同的，但针对0-based数组索引（而不是问题中给出的1-based）。 - j_random_hacker

Answer 1

我可以用O(klogk)的时间复杂度完成，假设k<

思路是维护一个最小堆，从头部（id==0）开始，即最小元素，并迭代地添加所有“新候选人”（对于给定的当前最低i而言，“候选人”是2i和2i+1）。

创建一个新的空最小堆，其中每个元素包含一个元组（x，i）- x是数组中的键，i是其索引。

set i = 0, currIdx = 0
heap.add((i,0))
while currIdx < k:
currIdx = currIdx + 1
   (x,i) = heap.popLowest()
   if i != 2i: //for i=2i=0, don't add it twice:
       heap.add((arr[2i],2i))
   heap.add((arr[2i+1],2i+1))
return heap.getTop()

时间复杂度为O(klogk)，堆上的每个操作都需要O(logN)（其中N是其当前大小），堆的最大大小为N=k，因此堆上的所有操作都是log(1) + log(2) + ... + log(k) = log((k)!)，它在O(klogk)中。

- amit

---

这是一种不错的方法，但令人惊讶的是它可以在O(k)时间内完成（正如您在评论中所说，但不在此答案中...？）：http://dl.acm.org/citation.cfm?id=176014。我还没有读完整篇论文，但它似乎很复杂和技术性，我发现学生们在有限的时间内需要从零开始解决这样的问题（直到1992年才成为计算机科学中的一个开放性问题！）令人惊讶！ - j_random_hacker

Answer 2

有两种方法：

1. O(k ln(n)) 时间复杂度。
2. O(k ln(k)) 时间复杂度 + O(K) 空间复杂度。

- Milan Patel

Answer 3

首先，你指的是“堆”，而不是“bst”（你描述的数据结构必须是一个堆，并不一定是bst）。

其次，这个问题可在O(k)时间内解决并不明显 - 直到1992年Frederickson给出了一个O(k)时间复杂度的算法。 我没有完全阅读这篇论文，但其中包含18页复杂的技术论证，我很惊讶奥林匹克组织者希望学生从零开始想出它！（或者他们可能已经期望学生熟悉该算法 - 在这种情况下，我会说(a) 这仍然要求相当多的知识; (b) 这不是一个非常好的问题。）

- j_random_hacker