题目

设计一个数字容器系统，可以实现以下功能：

在系统中给定下标处插入或者替换一个数字。
返回系统中给定数字的最小下标。

请你实现一个 NumberContainers 类：

NumberContainers() 初始化数字容器系统。
void change(int index, int number) 在下标 index 处填入 number 。如果该下标 index 处已经有数字了，那么用 number 替换该数字。
int find(int number) 返回给定数字 number 在系统中的最小下标。如果系统中没有 number ，那么返回 -1 。

示例：

输入： ["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"] [[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]] 输出： [null, -1, null, null, null, null, 1, null, 2]

解释： NumberContainers nc = new NumberContainers(); nc.find(10); // 没有数字 10 ，所以返回 -1 。 nc.change(2, 10); // 容器中下标为 2 处填入数字 10 。 nc.change(1, 10); // 容器中下标为 1 处填入数字 10 。 nc.change(3, 10); // 容器中下标为 3 处填入数字 10 。 nc.change(5, 10); // 容器中下标为 5 处填入数字 10 。 nc.find(10); // 数字 10 所在的下标为 1 ，2 ，3 和 5 。因为最小下标为 1 ，所以返回 1 。 nc.change(1, 20); // 容器中下标为 1 处填入数字 20 。注意，下标 1 处之前为 10 ，现在被替换为 20 。 nc.find(10); // 数字 10 所在下标为 2 ，3 和 5 。最小下标为 2 ，所以返回 2 。

提示：

1 <= index, number <= 10^9
调用 change 和 find 的 总次数 不超过 10^5 次。

解题思路

这道题的核心是实现两个功能：change 和 find。我们来分别分析它们的需求：

change(index, number):
- 这个操作需要我们能够根据 index 快速地存取或更新它对应的 number。
- index 的范围非常大（高达 109），这意味着我们不能使用一个常规的数组或 std::vector 来存储，否则会导致内存溢出。
- 对于这种“稀疏”的、按下标存取的需求（即大部分下标都是空的，只有少量下标有值），哈希表 (Hash Map) 是最理想的数据结构。在 C++ 中，我们可以使用 std::unordered_map<int, int>。
- 我们把这个哈希表命名为 indexToNum，其中 key 是 index，value 是 number。这样，change 操作中根据 index 找 number 的时间复杂度就是平均 O(1)。
find(number):
- 这个操作需要我们能够根据 number 快速地找到所有存储这个数字的 index，并返回其中最小的一个。
- 这意味着我们需要一个反向的映射：从 number 映射到一组 index。同样，哈希表也是一个很好的选择，我们可以用 std::unordered_map<int, ...>，其中 key 是 number。
- 关键在于 value 应该是什么数据结构。这个结构需要存放一个 number 对应的所有 index，并且能让我们快速找到其中的最小值。
  - 选项 A: std::vector<int>？我们可以把所有 index 存入一个动态数组。但是，每次 find时，为了找到最小值，都需要遍历整个数组（或者先排序），时间复杂度至少是 O(k)，其中 k 是这个 number 出现的次数。在最坏情况下，k 可能很大，导致超时。
  - 选项 B: std::priority_queue<int, std::vector<int>, std::greater<int>> (最小堆)？最小堆的堆顶永远是最小值，获取最小值的操作是 O(1)。但是，change 操作中存在一个复杂情况：当我们执行 change(1, 20) 时，原来在下标 1 处的数字 10 就被移除了。这意味着我们需要从 10 对应的索引集合中删除 1。而最小堆不支持高效的任意元素删除操作。所以我们需要考虑加入一个懒标记来实现
  - 选项 C: std::set<int>？ set 是一个基于红黑树的有序集合。它有以下完美契合我们需求的特性：
    - 自动排序：插入的 index 会被自动排序。
    - 快速查找最小值：集合中的第一个元素 (*s.begin()) 就是最小值，获取它的时间复杂度是 O(1)。
    - 高效的插入和删除：插入 (insert) 和删除 (erase) 的时间复杂度都是 O(log k)，其中 k 是集合中的元素数量。这比 vector 的 O(k) 要高效得多。

1. 哈希表 + 有序集合

我们使用两个主要的数据结构来跟踪信息：

indexToNum (一个 unordered_map<int, int>): 这个哈希表的作用是快速查找在任意 index 处存储的是哪个 number。key 是索引，value 是数字。
numToIndices (一个 unordered_map<int, set<int>>): 这个哈希表的作用是存储每个 number 出现的所有 index。key 是数字，value 是一个有序集合（std::set in C++）来存储所有该数字所在的索引。

实现逻辑

change(index, number):
- 检查旧值: 首先，我们用 indexToNum 查找 index 之前是否已经存有数字。
  - 如果存在 (old_number): 我们需要从 numToIndices[oldNumber] 的集合中删除 index。这是为了确保当我们查询 oldNumber 时，不会错误地返回这个已经被更改的 index。删除操作的复杂度是 O(log k)，其中 k 是 oldNumber 出现的次数。
  - 如果不存在: 说明这个 index 是第一次被赋值，无需删除操作。
- 更新新值:
  - 在 indexToNum 中，设置 index_map[index] = number。这是 O(1) 的操作。
  - 在 numToIndices 中，将 index 插入到 number 对应的集合中。这是 O(log k) 的操作。
find(number):
- 检查是否存在: 在 numToIndices 中查找 number 这个键。如果不存在，或者对应的集合为空，说明这个数字系统中没有，返回 -1。
- 返回最小值: 如果存在，由于 numToIndices[number] 是一个有序集合（std::set），它的第一个元素就是最小的索引。我们直接返回 *numToIndices[number].begin()。这个操作的复杂度是 O(1)。

复杂度分析

空间复杂度: $O(N)$，其中 $N$ 是 change 操作的总次数。因为在最坏的情况下，每个 change 都会创建一个新的索引。
change 时间复杂度: $O(log N)$。主要开销来自于在 set 中插入或删除元素。
find 时间复杂度: $O(1)$ (平均情况)。unordered_map 的查找是 $O(1)$ 平均，而 set::begin() 也是 $O(1)$。

2. 哈希表 + 最小堆（优先队列） + 懒惰删除

这个方法同样使用一个哈希表来记录每个位置的当前值，但用一个最小堆（Min-Heap）来快速获取每个数字的最小索引。

indexToNum (一个 unordered_map<int, int>): 和方法一完全一样，用来记录每个 index 当前对应的 number。
numToIndices (一个 unordered_map<int, priority_queue<int, vector<int>, greater<int>>>): 这个哈希表将每个 number 映射到一个最小堆。最小堆的特性是，它的堆顶（top()）永远是最小的元素。

它不直接支持高效删除任意一个元素。当我们执行 change(index, new_number) 时，我们需要从 old_number 的数据结构中移除 index，所以要加入懒标记。

实现逻辑

change 操作:
1. 更新 indexToNum[index] = number。
2. 将新的 index 推入 numToIndices[number] 的小顶堆中。
3. 我们不从旧数字的堆中删除旧的 index。这使得 change 操作非常快。
find(number) 操作:
1. 检查 number 是否存在于 numToIndices 中。如果不存在，或者对应的堆为空，返回 -1。
2. 查看堆顶元素 minIndex = numToIndices[number].top()。
3. 验证这个 minIndex 是否有效：
  - 使用 indexToNum 检查当前 minIndex 对应的值是否还是 number。
  - 如果 indexToNum[minIndex] == number，说明这个索引仍然有效，它就是我们要找的最小索引，返回它。
  - 如果 indexToNum[minIndex] 已经变成了另一个数字，说明这个索引是“过时的”或“无效的”。我们就从堆中弹出它 (pop())，然后重复步骤 2，直到找到一个有效的索引或者堆变空。
4. 如果循环结束时堆为空，说明所有和 number 关联的索引都已经被覆盖，因此返回 -1。

复杂度分析

空间复杂度: $O(C)$，其中 $C$ 是 change 操作的总次数。因为我们从不删除旧的索引，numToIndices 中的堆会不断增长。
change 时间复杂度: $O(log k)$，其中 $k$ 是堆的大小。这是插入堆所需的时间。
find 时间复杂度: $O(m log k)$，其中 $k$ 是堆的大小，$m$ 是需要弹出的无效（过期）元素的数量。在最坏的情况下，可能需要多次 pop 操作，但平均下来，这种方法通常非常高效，因为排序操作只在需要时隐式地进行。

具体代码

方法一

class NumberContainers {
private:
    // 存储 index -> number 的映射
    // 用于在 change 时快速找到旧的 number
    std::unordered_map<int, int> indexToNum;

    // 存储 number -> sorted indices 的映射
    // 使用 set 保证 index 自动排序，从而可以快速找到最小值
    std::unordered_map<int, std::set<int>> numToIndices;

public:
    NumberContainers() {
        // 构造函数中不需要做任何事情，成员变量会自动初始化
    }
    
    void change(int index, int number) {
        // 1. 处理旧的映射关系
        // 检查 index 是否已经存在于系统中
        if (indexToNum.count(index)) {
            // 获取该 index 对应的旧数字
            int oldNumber = indexToNum[index];
            
            // 从旧数字的索引集合中移除该 index
            numToIndices[oldNumber].erase(index);
            
            // 如果旧数字的索引集合变空了，可以从 map 中移除这个键以节省空间
            if (numToIndices[oldNumber].empty()) {
                numToIndices.erase(oldNumber);
            }
        }
        
        // 2. 建立新的映射关系
        // 更新 index -> number 的映射
        indexToNum[index] = number;
        
        // 将 index 加入新数字的索引集合中
        numToIndices[number].insert(index);
    }
    
    int find(int number) {
        // 检查系统中是否存在这个 number
        // .count() 检查 key 是否存在
        if (numToIndices.count(number)) {
            // 如果存在，由于 set 是有序的，第一个元素就是最小的 index
            return *numToIndices[number].begin();
        }
        
        // 如果系统中没有这个 number，返回 -1
        return -1;
    }
};

方法二

// 优化输入输出流，提高程序运行效率，常用于竞赛编程
static const auto io_sync_off = []() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();

class NumberContainers {
private:
    // 存储每个索引对应的数字，键为索引，值为数字
    std::unordered_map<int, int> indexToNum;
    // 存储每个数字对应的所有索引，键为数字，值为一个最小堆，堆中存放索引
    std::unordered_map<int, std::priority_queue<int, std::vector<int>, std::greater<int>>> numberToIndices;

public:
    NumberContainers() {}

    // 改变指定索引上的数字
    void change(int index, int number) {
        // 更新索引到数字的映射
        indexToNum[index] = number;
        // 将索引加入到新数字对应的最小堆中
        // 注意：不移除旧的索引，采用“惰性删除”策略
        numberToIndices[number].push(index);
    }

    // 查找某个数字对应的最小索引
    int find(int number) {
        // 如果数字不存在，直接返回-1
        if (numberToIndices.find(number) == numberToIndices.end()) {
            return -1;
        }

        auto& pq = numberToIndices[number];
        // 循环移除堆顶的无效索引（即其对应的数字已改变）
        while (!pq.empty() && indexToNum[pq.top()] != number) {
            pq.pop();
        }

        // 如果堆为空，说明没有有效索引，返回-1
        if (pq.empty()) {
            return -1;
        }
        
        // 返回最小且有效的索引
        return pq.top();
    }
};

2349. 设计数字容器系统

beautifulremi

题目

解题思路

1. 哈希表 + 有序集合

实现逻辑

复杂度分析

2. 哈希表 + 最小堆（优先队列） + 懒惰删除

实现逻辑

复杂度分析

具体代码

方法一

方法二