2102. 序列序数排名跟踪器

Hard

题目描述

一个风景区由其名称和吸引力分数表示，其中名称是所有位置中唯一的字符串，分数是一个整数。位置可以从最好到最差进行排名。分数越高，位置越好。如果两个位置的分数相等，那么按字典序较小的名称的位置更好。

你正在构建一个跟踪位置排名的系统，系统最初没有任何位置。它支持：

一次添加一个风景位置。
查询所有已添加位置中第 i 好的位置，其中 i 是系统被查询的次数（包括当前查询）。
- 例如，当系统第 4 次被查询时，它返回所有已添加位置中第 4 好的位置。

注意测试数据保证在任何时候，查询次数都不会超过添加到系统中的位置数量。

实现 SORTracker 类：

SORTracker() 初始化跟踪器系统。
void add(string name, int score) 向系统添加名为 name、分数为 score 的风景位置。
string get() 查询并返回第 i 好的位置，其中 i 是此方法被调用的次数（包括此次调用）。

示例 1：

输入
["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"]

约束条件：

name 由小写英文字母组成，且在所有位置中唯一。
1 <= name.length <= 10
1 <= score <= 10^5
在任何时候，对 get 的调用次数不超过对 add 的调用次数。
最多总共调用 4 * 10^4 次 add 和 get。

解题思路

这是一个动态维护第k小元素的问题，其中k随着查询次数递增。核心思路是使用双堆（优先队列）来维护排序状态。

解题思路：

排序规则：分数高的位置排名靠前，分数相同时按字典序小的排名靠前
双堆策略：
- 左堆（大根堆）：维护前 k+1 个最好的位置，其中 k 是当前查询次数
- 右堆（小根堆）：维护其余的位置
- 查询时返回左堆堆顶，然后调整堆的大小

操作流程：

add操作：将新位置加入左堆，如果左堆大小超过 k+1，将堆顶移到右堆
get操作：返回左堆堆顶（第k+1好的位置），然后k++，从右堆移一个元素到左堆以维护 k+1 个元素

实现要点：

需要自定义比较函数来处理分数和字典序的排序规则
C++中使用 priority_queue，Python中使用 heapq
注意堆的比较规则要与题目要求的排序规则匹配

代码实现

class SORTracker {
public:
    struct Location {
        string name;
        int score;
        Location(string n, int s) : name(n), score(s) {}
    };
    
    struct MaxHeapCmp {
        bool operator()(const Location& a, const Location& b) {
            if (a.score != b.score) return a.score < b.score;
            return a.name > b.name;
        }
    };
    
    struct MinHeapCmp {
        bool operator()(const Location& a, const Location& b) {
            if (a.score != b.score) return a.score > b.score;
            return a.name < b.name;
        }
    };
    
    priority_queue<Location, vector<Location>, MaxHeapCmp> left;  // max heap
    priority_queue<Location, vector<Location>, MinHeapCmp> right; // min heap
    int queryCount;
    
    SORTracker() {
        queryCount = 0;
    }
    
    void add(string name, int score) {
        left.push(Location(name, score));
        if (left.size() > queryCount + 1) {
            right.push(left.top());
            left.pop();
        }
    }
    
    string get() {
        string result = left.top().name;
        queryCount++;
        if (!right.empty()) {
            left.push(right.top());
            right.pop();
        }
        return result;
    }
};

import heapq

class SORTracker:

    def __init__(self):
        self.left = []  # max heap for top k+1 locations
        self.right = [] # min heap for remaining locations
        self.query_count = 0

    def add(self, name: str, score: int) -> None:
        # Add to left heap (negate score for max heap behavior)
        heapq.heappush(self.left, (score, name))
        
        # Maintain left heap size <= query_count + 1
        if len(self.left) > self.query_count + 1:
            heapq.heappush(self.right, (-self.left[0][0], self.left[0][1]))
            heapq.heappop(self.left)

    def get(self) -> str:
        result = self.left[0][1]
        self.query_count += 1
        
        # Move one element from right to left if possible
        if self.right:
            heapq.heappush(self.left, (-self.right[0][0], self.right[0][1]))
            heapq.heappop(self.right)
            
        return result

public class SORTracker {
    private class Location {
        public string Name;
        public int Score;
        public Location(string name, int score) {
            Name = name;
            Score = score;
        }
    }
    
    private class MaxHeapComparer : IComparer<Location> {
        public int Compare(Location x, Location y) {
            if (x.Score != y.Score) return y.Score.CompareTo(x.Score);
            return x.Name.CompareTo(y.Name);
        }
    }
    
    private class MinHeapComparer : IComparer<Location> {
        public int Compare(Location x, Location y) {
            if (x.Score != y.Score) return x.Score.CompareTo(y.Score);
            return y.Name.CompareTo(x.Name);
        }
    }
    
    private PriorityQueue<Location, Location> left;
    private PriorityQueue<Location, Location> right;
    private int queryCount;

    public SORTracker() {
        left = new PriorityQueue<Location, Location>(new MaxHeapComparer());
        right = new PriorityQueue<Location, Location>(new MinHeapComparer());
        queryCount = 0;
    }
    
    public void Add(string name, int score) {
        var location = new Location(name, score);
        left.Enqueue(location, location);
        
        if (left.Count > queryCount + 1) {
            var top = left.Dequeue();
            right.Enqueue(top, top);
        }
    }
    
    public string Get() {
        string result = left.Peek().Name;
        queryCount++;
        
        if (right.Count > 0) {
            var top = right.Dequeue();
            left.Enqueue(top, top);
        }
        
        return result;
    }
}

var SORTracker = function() {
    this.left = new MinPriorityQueue({
        compare: (a, b) => {
            if (a.score !== b.score) return b.score - a.score;
            return a.name.localeCompare(b.name);
        }
    });
    this.right = new MinPriorityQueue({
        compare: (a, b) => {
            if (a.score !== b.score) return a.score - b.score;
            return b.name.localeCompare(a.name);
        }
    });
    this.queryCount = 0;
};

SORTracker.prototype.add = function(name, score) {
    this.left.enqueue({name: name, score: score});
    
    if (this.left.size() > this.queryCount + 1) {
        this.right.enqueue(this.left.dequeue());
    }
};

SORTracker.prototype.get = function() {
    const result = this.left.front().name;
    this.queryCount++;
    
    if (!this.right.isEmpty()) {
        this.left.enqueue(this.right.dequeue());
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
add	O(log n)	O(1)
get	O(log n)	O(1)
总体	O(m log n)	O(n)

其中 n 是添加的位置数量，m 是操作总数。空间复杂度为 O(n) 用于存储所有位置。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目