序列顺序查询

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

难度: Hard

一个观光景点由它的名字 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 <= 105
  • 任意时刻，调用 get 的次数都不超过调用 add 的次数。
  • 总共 调用 add 和 get 不超过 4 * 104 

Submission

运行时间: 473 ms

内存: 38.7 MB

from sortedcontainers import SortedList
class SORTracker:

    def __init__(self):
        self.arr=SortedList()
        self.n=0


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

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



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

Explain

此题解利用了sortedcontainers库中的SortedList数据结构，以维持景点的有序状态。每个景点以元组(-score, name)的形式存储，这样可以确保景点在列表中自动按照评分降序和字典序升序排列。添加操作直接将景点元组插入SortedList，由于SortedList内部机制，插入后列表仍然保持有序。查询操作则根据累积的查询次数n（self.n），从SortedList中获取第n好的景点。

时间复杂度: add: O(log n), get: O(1)

空间复杂度: O(n)

from sortedcontainers import SortedList

class SORTracker:

    def __init__(self):
        self.arr=SortedList() # 初始化一个SortedList存储景点，保持有序
        self.n=0 # 用于记录get操作的调用次数


    def add(self, name: str, score: int) -> None:
        # 向SortedList中添加一个元组，元组的第一个元素是-score使得排序时按照score降序
        self.arr.add((-score,name))

    def get(self) -> str:
        # 根据调用次数获取对应排名的景点名称
        self.n+=1
        return self.arr[self.n-1][1]

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

Explore

SortedList数据结构通过维护一个内部平衡二叉搜索树（通常是红黑树或AVL树）来实现其功能。因此，在SortedList中插入一个元素的时间复杂度为O(log n)，其中n是列表中的元素数量。查询（包括按索引访问）操作的时间复杂度也是O(log n)。这使得SortedList在处理需要频繁插入和随机访问的场景下非常高效。

SortedList在进行元素比较时会依次比较元组中的每个元素。在这个问题的上下文中，元组的第一个元素是-score（评分的相反数），这样评分高的元素会被视为较小（因为负数越小其原始评分越高）。当两个景点的-score相等时，SortedList会比较元组的第二个元素，即景点的名字。因为字符串比较是按字典序进行的，所以这自然地实现了在评分相同的情况下按字典序对景点名进行排序。

SortedList被选择用于这个应用主要因为它同时支持高效的插入和精确索引访问。优先队列（通常实现为二叉堆）虽然可以高效地支持插入和获取最小（或最大）元素，但它不支持O(log n)时间复杂度的随机位置访问。平衡二叉搜索树虽然能提供这两种操作的高效支持，但直接使用现成的SortedList库可以简化实现并减少出错的可能性。SortedList内部可能就是使用类似平衡二叉搜索树的结构实现的，它提供了现成的、经过优化的方法用于管理按顺序排列的元素，这些方法正好符合题目的需求。