推 Meaverzt: 大師 02/08 22:22
推 Furina: 大師 02/08 22:30
2349. Design a Number Container System
## 思路
用hash table 紀錄index最後的number
每個number也都建一個minHeap, 存index
change: 更新table、把index加到heap
find: 檢查該值的heap, 如果top的index對應到的值不同就丟掉
## Code
```cpp
class NumberContainers {
public:
NumberContainers() {
}
void change(int index, int number) {
table_[index] = number;
heaps_[number].push(index);
}
int find(int number) {
if (!heaps_.count(number)) return -1;
while (!heaps_[number].empty()) {
int curr = heaps_[number].top();
if (table_[curr] == number) return curr;
heaps_[number].pop();
}
return -1;
}
private:
unordered_map<int, priority_queue<int, vector<int>, greater<int>>>
heaps_;
unordered_map<int, int> table_;
};
/**
* Your NumberContainers object will be instantiated and called as such:
* NumberContainers* obj = new NumberContainers();
* obj->change(index,number);
* int param_2 = obj->find(number);
*/
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 94.156.149.161 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1739024522.A.DF1.html