布鲁汉堡滇缅

设计题目有N个运动员在跑马拉松，他们的跑步距离被

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

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

运动员。 BST？

谢谢楼主！真是好人

😄，
觉得有用的给我点大米吧

既然是实时查询，那么应该保存每个运动员的位置和速度，位置简单；
如果是平均速度，位置就能代替速度；如果是瞬时速度，用位置的导数；
然后取最大的三个，我觉得总是要把所有运动员O(n)扫一遍的吧？有没有更好的方法？

Method 1. HashMap<player, distance> + BST/treeMap<distance, player, rank>
      - lookup location O(1)
      - lookup rank O(N)
      - update O(N)
      - lookup M fastest O(BST height + M)
Method 2. Doubly LinkedList<Player, distance, Rank> + HashMap<Player, Player Node>
      - lookup location O(1)
      - lookup rank O(1)
      - update O(N)
      - lookup M fastest O(M)
但是这道题目感觉要考虑实际use case，如果update很频繁（因为可以实时获取所有人的距离），那么大部分情况下，排名不会改变太多，method 2 update就是O(1)的，所以看起来第二个方法更好呀。
希望可以和楼主讨论下。