时间轴

2025-09-17

init

题目：

P2349 设计数字容器系统

https://leetcode.cn/problems/design-a-number-container-system/description/?envType=daily-question&envId=2025-09-17

这题主要利用空间换时间的思想，根据提示的 index 和 number 的大小范围可以断定暴力解法肯定 TLE，而事实也的确如此。
利用 set 的特性：std::set 内部是平衡二叉搜索树（通常是红黑树）。树中 最小元素总是在最左边 → set.begin() 指向最左叶子节点。因此 rbegin() 则返回 最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <map>
#include <set>
class NumberContainers {
public:
  NumberContainers() {}

  void change(int index, int number) {

    if (map.count(index)) { // map中原本有该index
      int last_number = map[index];
      min_map[last_number].erase(index);
    }
    map[index] = number;
    min_map[number].insert(index);
  }

  int find(int number) {
    if (min_map.count(number) && !min_map[number].empty()) {
      return *min_map[number].begin();
    } else {
      return -1;
    }
  }

private:
  std::map<int, int> map;
  std::map<int, std::set<int>> min_map;
};

/**
 * Your NumberContainers object will be instantiated and called as such:
 *      NumberContainers* obj = new NumberContainers();
 * obj->change(index,number);
 * int param_2 = obj->find(number);
 */