HardRating 2159
2102. Sequentially Ordinal Rank Tracker
designheap-priority-queuedata-streamordered-set
解題說明
Sequentially Ordinal Rank Tracker
題目描述: 設計一個系統追蹤景點排名。支援兩個操作:add(name, score) 加入一個景點,get() 回傳第 i 好的景點名稱(第 i 次呼叫 get 回傳第 i 好的)。排序規則:分數高的較好;分數相同時名稱字典序小的較好。
解題思路: 使用兩個堆(或一個有序集合)維護第 k 名的邊界。
方法一:使用 C++ 的 set,配合一個迭代器追蹤當前查詢位置。
- 使用
set<pair<int, string>>,其中 pair 為(-score, name)使得自然排序即為所需的排名順序(分數降序,同分名稱升序)。 - 維護一個迭代器
it指向下一次 get() 應該回傳的元素。初始時it = s.end()。 - add(name, score):插入新元素。若新元素排在
it之前(或 it 指向 end),則it--。 - get():回傳
it指向的元素,然後it++。
C++ 解法
複雜度分析
時間複雜度:add O(log n),get O(1) — set 插入為 O(log n),迭代器移動為 O(1)。
空間複雜度:O(n) — 存儲所有已加入的景點。
虛擬碼
1. Maintain an ordered set of (-score, name) pairs. 2. Keep an iterator `it` pointing to the next element to return. 3. ADD(name, score): a. Insert (-score, name) into set. b. If the new element is positioned before `it` (or it was end), decrement it. 4. GET(): a. Return the name at `it`, then increment it.
其他解法
-
雙堆法:維護一個最大堆(存前 k 名)和一個最小堆(存其餘)。get 每次從最大堆取出最差的元素(即第 k 名),下次 k 增加 1。add 時根據新元素與堆頂的比較決定放入哪個堆。每次操作 O(log n)。
-
陣列 + 二分插入:將所有景點存在有序陣列中,用二分搜尋找到插入位置。add O(n)(需要移動元素),get O(1)。適合查詢頻繁但插入少的場景。
延伸思考
- 若需要支援刪除景點(remove),set 迭代器的維護需要注意什麼?
- 若 get() 不是按順序查詢第 1、2、3... 名,而是任意查詢第 k 名,資料結構需要如何調整?
- 若分數會動態更新(同一景點的分數可能變化),如何高效處理?