f*****s 发帖数: 141 | 1 Given a Binary Search Tree, write a program to print the kth smallest
element without using any static/global variable.
什么方法最好? |
s*******s 发帖数: 1568 | |
f*****s 发帖数: 141 | 3 In-order traverse always generate value-sorted output, right? So, just use
in-order searching, traverse from 1st element until the k-th element. Is
this correct? |
d*j 发帖数: 13780 | 4 肯定是对的, 人家又要问 有没有 better way ?
这也是肯定的
【在 f*****s 的大作中提到】 : In-order traverse always generate value-sorted output, right? So, just use : in-order searching, traverse from 1st element until the k-th element. Is : this correct?
|
b******v 发帖数: 1493 | 5 如果k<=n/2,可以从最小元开始做k-1次FindNext
如果k>n/2,可以从最大元开始做n-k次FindPrevious
时间复杂度O(k'*log(n)),其中k' = min{k, n-k+1}
【在 f*****s 的大作中提到】 : Given a Binary Search Tree, write a program to print the kth smallest : element without using any static/global variable. : 什么方法最好?
|
k*******d 发帖数: 1340 | 6 用in-order search能不使用global variable吗?search的时候得用个变量来记录这搜
索到第几个元素了吧?然后当这个变量等于k的时候,停止搜索。这个变量算是global
variable/static variable吗?
我觉得如果要用递归实现这个遍历的话难以避免要用到这个global variable/static
variable吧, 所以这个题的关键应该是不用递归来实现inorder遍历吧,答案可以
google到 |
f*********g 发帖数: 207 | 7 isn't it k'+o(log(n))?
【在 b******v 的大作中提到】 : 如果k<=n/2,可以从最小元开始做k-1次FindNext : 如果k>n/2,可以从最大元开始做n-k次FindPrevious : 时间复杂度O(k'*log(n)),其中k' = min{k, n-k+1}
|