狗狗家

lx5945 发表于 2017-10-13 08:42
我觉得这道题实现倒是不困难，但是就是一个相对好，可以相对满意的答案就比较难，请问大家对这道题都有什么 ...

我想的arraylist 或者priorityqueue时间复杂度都很高…

lx5945 发表于 2017-10-13 08:42
我觉得这道题实现倒是不困难，但是就是一个相对好，可以相对满意的答案就比较难，请问大家对这道题都有什么 ...

我想的arraylist 或者priorityqueue时间复杂度都很高…

好像有一种tree, 每个node里面记录score和左边有多少node, 如果设计成self-balanced, 可以达到log(n) update 和 getByRank

qpalzm0827 发表于 2017-10-15 04:35
好像有一种tree, 每个node里面记录score和左边有多少node, 如果设计成self-balanced, 可以达到log(n) updat ...

想问层住，如果用你说的这种tree的话，如何在log n 内完成update的操作？

张欣 发表于 2017-10-13 09:57
我想的arraylist 或者priorityqueue时间复杂度都很高…

我觉得用arraylist和一个hashmap可以做到update操作在O(n)而getRank操作在O(1)内完成

waxc 发表于 2017-10-16 01:21
我觉得用arraylist和一个hashmap可以做到update操作在O(n)而getRank操作在O(1)内完成

对，就是update时间复杂度o（n）感觉有点高，如果update得多的话

waxc 发表于 2017-10-16 01:21
我觉得用arraylist和一个hashmap可以做到update操作在O(n)而getRank操作在O(1)内完成

而且除了加入arraylist 会cost o(n)外，找出找哪个位置插入，binary search也会花费nlog(n)

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

waxc 发表于 2017-10-16 02:24
我的意思是，用arraylist和hashmap的话，找的部分可以用hashmap实现，找位置的部分也只需要O(n)，原理跟i ...

最后时间是o（n）没错，找位置二分查找复杂度我说错了 应该是log（n）

感觉如果分数在一个区间内的话，可以用bucket sort