两个hashtable，一个是index->number，另外一个是number -> {index}，使用treeset，自动排序。
时间复杂度：change O(logn)，find O(1)
空间复杂度：O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class NumberContainers { public: NumberContainers() {} void change(int index, int number) { if (m_.count(index)) { auto it = idx_.find(m_[index]); it->second.erase(index); if (it->second.empty()) idx_.erase(it); } m_[index] = number; idx_[number].insert(index); } int find(int number) { auto it = idx_.find(number); if (it == end(idx_)) return -1; return *begin(it->second); } private: unordered_map<int, int> m_; // index -> num unordered_map<int, set<int>> idx_; // num -> {index} }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment