What data structure is optimal for tracking rankings in this problem?

A min-heap (priority queue) is optimal for tracking rankings because it allows efficient addition and removal of elements while maintaining order.

How do I handle ties in location scores?

In the case of ties, locations with lexicographically smaller names should be ranked higher. This can be achieved by storing both score and name in the heap and using lexicographical comparisons when scores are equal.

What is the time complexity for adding a location?

The time complexity for adding a location is O(log N), where N is the number of locations already in the system, due to the heap insertion operation.

Can the system handle a large number of locations?

Yes, the system can efficiently handle up to 4 * 10^4 calls to add and get operations, thanks to the efficient heap operations for both insertion and querying.

How does GhostInterview help with this problem?

GhostInterview provides a clear path for designing efficient ranking systems using heaps, offering step-by-step guidance on how to optimize for both score and lexicographical order.

#2102

Hard

auto_awesome堆

LeetCode 题解工作台

序列顺序查询

一个观光景点由它的名字 name 和景点评分 score 组成，其中 name 是所有观光景点中唯一的字符串， score 是一个整数。景点按照最好到最坏排序。景点评分越高，这个景点越好。如果有两个景点的评分一样，那么字典序较小的景点更好。你需要搭建一个系统，查询景点的排名。初始时系统…

设计堆（优先队列）数据流有序集合

题目描述

一个观光景点由它的名字 name 和景点评分 score 组成，其中 name 是所有观光景点中唯一的字符串，score 是一个整数。景点按照最好到最坏排序。景点评分越高，这个景点越好。如果有两个景点的评分一样，那么 字典序较小 的景点更好。

你需要搭建一个系统，查询景点的排名。初始时系统里没有任何景点。这个系统支持：

添加景点，每次添加一个景点。
查询已经添加景点中第 i 好的景点，其中 i 是系统目前位置查询的次数（包括当前这一次）。
- 比方说，如果系统正在进行第 4 次查询，那么需要返回所有已经添加景点中第 4 好的。

注意，测试数据保证 任意查询时刻 ，查询次数都 不超过 系统中景点的数目。

请你实现 SORTracker 类：

SORTracker() 初始化系统。
void add(string name, int score) 向系统中添加一个名为 name 评分为 score 的景点。
string get() 查询第 i 好的景点，其中 i 是目前系统查询的次数（包括当前这次查询）。

示例：

输入：
["SORTracker", "add", "add", "get", "add", "get", "add", "get", "add", "get", "add", "get", "get"]
[[], ["bradford", 2], ["branford", 3], [], ["alps", 2], [], ["orland", 2], [], ["orlando", 3], [], ["alpine", 2], [], []]
输出：
[null, null, null, "branford", null, "alps", null, "bradford", null, "bradford", null, "bradford", "orland"]

解释：
SORTracker tracker = new SORTracker(); // 初始化系统
tracker.add("bradford", 2); // 添加 name="bradford" 且 score=2 的景点。
tracker.add("branford", 3); // 添加 name="branford" 且 score=3 的景点。
tracker.get();              // 从好到坏的景点为：branford ，bradford 。
                            // 注意到 branford 比 bradford 好，因为它的 评分更高 (3 > 2) 。
                            // 这是第 1 次调用 get() ，所以返回最好的景点："branford" 。
tracker.add("alps", 2);     // 添加 name="alps" 且 score=2 的景点。
tracker.get();              // 从好到坏的景点为：branford, alps, bradford 。
                            // 注意 alps 比 bradford 好，虽然它们评分相同，都为 2 。
                            // 这是因为 "alps" 字典序 比 "bradford" 小。
                            // 返回第 2 好的地点 "alps" ，因为当前为第 2 次调用 get() 。
tracker.add("orland", 2);   // 添加 name="orland" 且 score=2 的景点。
tracker.get();              // 从好到坏的景点为：branford, alps, bradford, orland 。
                            // 返回 "bradford" ，因为当前为第 3 次调用 get() 。
tracker.add("orlando", 3);  // 添加 name="orlando" 且 score=3 的景点。
tracker.get();              // 从好到坏的景点为：branford, orlando, alps, bradford, orland 。
                            // 返回 "bradford".
tracker.add("alpine", 2);   // 添加 name="alpine" 且 score=2 的景点。
tracker.get();              // 从好到坏的景点为：branford, orlando, alpine, alps, bradford, orland 。
                            // 返回 "bradford" 。
tracker.get();              // 从好到坏的景点为：branford, orlando, alpine, alps, bradford, orland 。
                            // 返回 "orland" 。

提示：

name 只包含小写英文字母，且每个景点名字互不相同。
1 <= name.length <= 10
1 <= score <= 10⁵
任意时刻，调用 get 的次数都不超过调用 add 的次数。
总共调用 add 和 get 不超过 4 * 10⁴

lightbulb

解题思路

方法一：有序集合

我们可以使用有序集合来存储景点，用一个变量 $i$ 来记录当前查询的次数，初始时 $i = -1$ 。

调用 add 方法时，我们将景点的评分取负数，这样就可以使用有序集合按照评分从大到小排序，如果评分相同，按照景点名字的字典序从小到大排序。

调用 get 方法时，我们将 $i$ 加一，然后返回有序集合中第 $i$ 个景点的名字。

每次操作的时间复杂度为 $O(\log n)$ ，其中 $n$ 为已添加的景点数。空间复杂度为 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class SORTracker:

    def __init__(self):
        self.sl = SortedList()
        self.i = -1

    def add(self, name: str, score: int) -> None:
        self.sl.add((-score, name))

    def get(self) -> str:
        self.i += 1
        return self.sl[self.i][1]


# Your SORTracker object will be instantiated and called as such:
# obj = SORTracker()
# obj.add(name,score)
# param_2 = obj.get()

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of efficient data structure usage like heaps for ranking systems.
question_mark
Expect the candidate to connect the problem with handling dynamic data streams effectively.
question_mark
Candidates should mention managing both numeric scores and string-based lexicographic comparisons in their solution.

warning

常见陷阱

外企场景

error
Mismanaging ties in score rankings could lead to incorrect outputs. Remember to use lexicographical order when scores are equal.
error
Overcomplicating the design by introducing unnecessary data structures when a simple heap would suffice.
error
Failing to consider the size of the data set and optimizing for query performance could result in inefficiency.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Tracking the top-k locations instead of just the best location.
arrow_right_alt
Handling locations with additional attributes besides name and score.
arrow_right_alt
Modifying the problem to track and return the rankings for multiple queries at once.

help

常见问题

外企场景

继续练习

#2034 股票价格波动 #1825 求出 MK 平均值 #1912 设计电影租借系统