序列顺序查询

2102. 序列顺序查询

一个观光景点由它的名字 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⁴

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class SORTracker { public: SORTracker() { } void add(string name, int score) { } string get() { } }; /** * Your SORTracker object will be instantiated and called as such: * SORTracker* obj = new SORTracker(); * obj->add(name,score); * string param_2 = obj->get(); */

java 解法, 执行用时: 286 ms, 内存消耗: 65 MB, 提交时间: 2023-09-11 15:04:15

class SORTracker {
    List<String> names = new ArrayList<>();
    List<Integer> scores = new ArrayList<>();
    Comparator<Integer> comparator = Comparator.comparing(scores::get)
            .thenComparing(Comparator.comparing(names::get).reversed());
    Queue<Integer> minHeap = new PriorityQueue<>(comparator);
    Queue<Integer> maxHeap = new PriorityQueue<>(comparator.reversed());

    public SORTracker() {
    }

    public void add(String name, int score) {
        names.add(name);
        scores.add(score);
        minHeap.offer(names.size() - 1);
        maxHeap.offer(minHeap.poll());
    }

    public String get() {
        minHeap.offer(maxHeap.poll());
        return names.get(minHeap.peek());
    }
}

/**
 * Your SORTracker object will be instantiated and called as such:
 * SORTracker obj = new SORTracker();
 * obj.add(name,score);
 * String param_2 = obj.get();
 */

cpp 解法, 执行用时: 472 ms, 内存消耗: 145.8 MB, 提交时间: 2023-09-11 15:03:29

class SORTracker {
    set<pair<int, string>> s;
    set<pair<int, string>>::iterator cur;

public:
    SORTracker() {
        s.emplace(0, ""); // 哨兵
        cur = s.begin();
    }

    void add(string name, int score) {
        pair<int, string> p = {-score, name};
        s.emplace(p);
        if (p < *cur) --cur;
    }

    string get() {
        return cur++->second;
    }
};

/**
 * Your SORTracker object will be instantiated and called as such:
 * SORTracker* obj = new SORTracker();
 * obj->add(name,score);
 * string param_2 = obj->get();
 */

python3 解法, 执行用时: 636 ms, 内存消耗: 39.5 MB, 提交时间: 2023-09-11 15:02:34

from sortedcontainers import SortedList

class SORTracker:
    def __init__(self):
        self.d = SortedList()
        self.i = 0

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

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


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

golang 解法, 执行用时: 356 ms, 内存消耗: 21.1 MB, 提交时间: 2023-09-11 15:01:49

type pair struct {
	score int
	name  string
}

func compare(x, y interface{}) int {
	a, b := x.(pair), y.(pair)
	if a.score > b.score || a.score == b.score && a.name < b.name {
		return -1
	}
	return 1
}

type SORTracker struct {
	*redblacktree.Tree
	cur redblacktree.Iterator
}

func Constructor() SORTracker {
	root := redblacktree.NewWith(compare)
	root.Put(pair{}, nil) // 哨兵
	return SORTracker{root, root.IteratorAt(root.Left())}
}

func (t *SORTracker) Add(name string, score int) {
	p := pair{score, name}
	t.Put(p, nil)
	if compare(p, t.cur.Key()) < 0 {
		t.cur.Prev() // 移动至前一个元素
	}
}

func (t *SORTracker) Get() string {
	name := t.cur.Key().(pair).name
	t.cur.Next() // 移动至下一个元素
	return name
}


/**
 * Your SORTracker object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(name,score);
 * param_2 := obj.Get();
 */

上一题

下一题

详情