咕果MTV onsite

大木虫 发表于 2018-11-12 08:13
对，是BST。我散要务就是这么写的

不过这样update score得handle BST的node deletion, 的确不容易写.

atlantic7200 发表于 2018-11-14 10:10
不过这样update score得handle BST的node deletion, 的确不容易写.

对，涉及到普通deletion以及对count的一路修改，比较麻烦

kaihaohust 发表于 2018-11-9 22:23
第一题可以先make assumption， 考虑到score是int类型
1. 如果score在一定范围比如0-100，可以用类似count ...

第一个解感觉没问题，如果score在一定区间内，会非常有效
第二个解不是很懂。  segemnt 是求区间最大最小值的。
而题目要求的是第k大。segment的用处在哪呢  能否解释下

hashheap是可以解决的
或者纯更新heap也是可以的

foryousee 发表于 2018-11-9 22:07
应该就是一个带左子数数量的二叉查找数。成绩是key，学号反而是value

谢谢层主提供思路   bst完美解决第k大的问题。
只要在每个bst的node 上 再维护一个count。就行
每次删除node的时候，依次update 跟它相连的parent node  的 count - 1
每次加入node的时候，依次update 跟它相连的parent node  的 count + 1
update 总耗费时间 2lgn
query 也是 lgn

hlckl123456 发表于 2018-11-16 06:35
第一个解感觉没问题，如果score在一定区间内，会非常有效
第二个解不是很懂。  segemnt 是求区间最大最 ...

for example.
第一层是            0-2000, 100个
                         /                        \
第二层是   0-1000, 40个，           1000-2000， 60个
               /                 \                          /                       \
第三层是0-500，10个，500-1000，30个，1000-1500，40个，1500-2000，20个

.....
segment tree 每个节点是subtree的数量，其实也是可以做的，第12大的肯定在500-1000，keep looking for subtree
ps 主要我是python选手没有可以用的Balanced BST可以直接用

kaihaohust 发表于 2018-11-16 07:37
for example.
第一层是            0-2000, 100个
                         /                        ...

segment tree 真的很万能。谢谢层主。

hlckl123456 发表于 2018-11-16 06:48
谢谢层主提供思路   bst完美解决第k大的问题。
只要在每个bst的node 上 再维护一个count。就行
每次删 ...

这个count是指的小于当前节点指的所有节点数量吗？如果是的话，我不太确定仅仅update 从root到target node上这一支的count是足够的啊？这一支整个右半边的所有节点不应该都更新吗？

Heinrich 发表于 2018-11-30 02:51
这个count是指的小于当前节点指的所有节点数量吗？如果是的话，我不太确定仅仅update 从root到target nod ...

对 没错 字数字数字数

hlckl123456 发表于 2018-12-1 00:07
对 没错 字数字数字数

没……没错的意思就是确实是要去更新整个右半边树？

Heinrich 发表于 2018-12-1 00:11
没……没错的意思就是确实是要去更新整个右半边树？

只需要更新它的parent 的count啊，子树的count 还是不变的。
这个就是在第二问求top k的时候会用到。这样的时间复杂度是lgk