糖糖版烧鹅# pets - 心有所宠
a*r
1 楼
假设BST每个key都是 >=0 的整数，而且不重复，有没有时间复杂度是O(lgn)的算法来
search kth smallest key. inorder traversal似乎不能满足要求。
search kth smallest key. inorder traversal似乎不能满足要求。
c*e
2 楼
奔一张糖糖版正面向上烧鹅。
肚子上的伤口还没有彻底好，还要吃一周的抗生素，下周还要去复诊，借人气求祝福，
希望糖的伤口尽快痊愈。
小丫头精神状态非常好，能吃能拉，没见过带着保护罩还能玩捉尾巴游戏的喵。
肚子上的伤口还没有彻底好，还要吃一周的抗生素，下周还要去复诊，借人气求祝福，
希望糖的伤口尽快痊愈。
小丫头精神状态非常好，能吃能拉，没见过带着保护罩还能玩捉尾巴游戏的喵。
r*k
3 楼
bst额外记一个小于等于当前key的点的个数
也就是左子树的节点个数，就可以了吧
【在 a********r 的大作中提到】
: 假设BST每个key都是 >=0 的整数，而且不重复，有没有时间复杂度是O(lgn)的算法来
: search kth smallest key. inorder traversal似乎不能满足要求。
也就是左子树的节点个数，就可以了吧
【在 a********r 的大作中提到】
: 假设BST每个key都是 >=0 的整数，而且不重复，有没有时间复杂度是O(lgn)的算法来
: search kth smallest key. inorder traversal似乎不能满足要求。
c*e
4 楼
这姿势多妩媚啊，自叹不如啊
a*r
5 楼
但是树已经是建好的,重建的话至少要O (n)
时间。所以说能不能优化, 整数inorder search的时间是关键。
【在 r*******k 的大作中提到】
: bst额外记一个小于等于当前key的点的个数
: 也就是左子树的节点个数，就可以了吧
时间。所以说能不能优化, 整数inorder search的时间是关键。
【在 r*******k 的大作中提到】
: bst额外记一个小于等于当前key的点的个数
: 也就是左子树的节点个数，就可以了吧
R*0
6 楼
伤口看着好心疼啊！糖糖快快好起来吧~
【在 c****e 的大作中提到】
: 这姿势多妩媚啊，自叹不如啊
【在 c****e 的大作中提到】
: 这姿势多妩媚啊，自叹不如啊
s*x
7 楼
参见 augmented data structure in algorithm introduction, 楼上已给出答案。
I do not think they ask you not modifying the tree.
【在 a********r 的大作中提到】
: 但是树已经是建好的,重建的话至少要O (n)
: 时间。所以说能不能优化, 整数inorder search的时间是关键。
c*x
8 楼
bless.会很快好的~
【在 c****e 的大作中提到】
: 奔一张糖糖版正面向上烧鹅。
: 肚子上的伤口还没有彻底好，还要吃一周的抗生素，下周还要去复诊，借人气求祝福，
: 希望糖的伤口尽快痊愈。
: 小丫头精神状态非常好，能吃能拉，没见过带着保护罩还能玩捉尾巴游戏的喵。
【在 c****e 的大作中提到】
: 奔一张糖糖版正面向上烧鹅。
: 肚子上的伤口还没有彻底好，还要吃一周的抗生素，下周还要去复诊，借人气求祝福，
: 希望糖的伤口尽快痊愈。
: 小丫头精神状态非常好，能吃能拉，没见过带着保护罩还能玩捉尾巴游戏的喵。
r*k
9 楼
不加信息是不可能的啊
如果有n个node，求第n个数，
你不遍历前n-1个数，你怎么知道哪个是第n个？
必然是o(n)啊
想到做lgn，必然不会遍历所有的，
剪枝需要额外的信息
【在 a********r 的大作中提到】
: 但是树已经是建好的,重建的话至少要O (n)
: 时间。所以说能不能优化, 整数inorder search的时间是关键。
如果有n个node，求第n个数，
你不遍历前n-1个数，你怎么知道哪个是第n个？
必然是o(n)啊
想到做lgn，必然不会遍历所有的，
剪枝需要额外的信息
【在 a********r 的大作中提到】
: 但是树已经是建好的,重建的话至少要O (n)
: 时间。所以说能不能优化, 整数inorder search的时间是关键。
C*e
10 楼
bless
l*b
11 楼
我在想能不能通过level order的遍历 然后数数 大概判断一下kth在左还是在右 这样
大概就是logN了 但是仔细想了半天 思路不通。。。 而且恐怕事先不知道有多少个
node且bst不是balanced
。。。个人觉得 可能就还是线性时间复杂度吧- -
大概就是logN了 但是仔细想了半天 思路不通。。。 而且恐怕事先不知道有多少个
node且bst不是balanced
。。。个人觉得 可能就还是线性时间复杂度吧- -
b*a
12 楼
bless
r*k
13 楼
要是balanced或者是满的
倒是可以猜猜
否则，普通的bst，必然是线性的
【在 l*********b 的大作中提到】
: 我在想能不能通过level order的遍历 然后数数 大概判断一下kth在左还是在右 这样
: 大概就是logN了 但是仔细想了半天 思路不通。。。 而且恐怕事先不知道有多少个
: node且bst不是balanced
: 。。。个人觉得 可能就还是线性时间复杂度吧- -
倒是可以猜猜
否则，普通的bst，必然是线性的
【在 l*********b 的大作中提到】
: 我在想能不能通过level order的遍历 然后数数 大概判断一下kth在左还是在右 这样
: 大概就是logN了 但是仔细想了半天 思路不通。。。 而且恐怕事先不知道有多少个
: node且bst不是balanced
: 。。。个人觉得 可能就还是线性时间复杂度吧- -
r*a
14 楼
哎呀，好疼，bless赶紧长好~
【在 c****e 的大作中提到】
: 奔一张糖糖版正面向上烧鹅。
: 肚子上的伤口还没有彻底好，还要吃一周的抗生素，下周还要去复诊，借人气求祝福，
: 希望糖的伤口尽快痊愈。
: 小丫头精神状态非常好，能吃能拉，没见过带着保护罩还能玩捉尾巴游戏的喵。
【在 c****e 的大作中提到】
: 奔一张糖糖版正面向上烧鹅。
: 肚子上的伤口还没有彻底好，还要吃一周的抗生素，下周还要去复诊，借人气求祝福，
: 希望糖的伤口尽快痊愈。
: 小丫头精神状态非常好，能吃能拉，没见过带着保护罩还能玩捉尾巴游戏的喵。
b*r
15 楼
对头。如果BST退化成一个单链表，没法再LOGN里面完成。
【在 r*******k 的大作中提到】
: 要是balanced或者是满的
: 倒是可以猜猜
: 否则，普通的bst，必然是线性的
【在 r*******k 的大作中提到】
: 要是balanced或者是满的
: 倒是可以猜猜
: 否则，普通的bst，必然是线性的
z*e
16 楼
小脸蛋太可爱了！
伤口快快好！
【在 c****e 的大作中提到】
: 这姿势多妩媚啊，自叹不如啊
伤口快快好！
【在 c****e 的大作中提到】
: 这姿势多妩媚啊，自叹不如啊
w*u
17 楼
bless伤口快快好！
k*e
18 楼
好娇媚～
【在 c****e 的大作中提到】
: 这姿势多妩媚啊，自叹不如啊
【在 c****e 的大作中提到】
: 这姿势多妩媚啊，自叹不如啊
相关阅读