标签： 懒删除

目标

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

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

请你实现一个 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 次。

思路

设计一个数字容器，能够将数字更新到指定下标，并且查询数字的最小下标。

使用最小堆维护相同数字的最小下标，同时使用哈希表记录下标对应的数字。查询最小下标时，如果下标上的数字不是查询的数字则从堆中删除。

代码

/**
 * @date 2025-09-17 8:48
 */
public class NumberContainers {

    private final Map<Integer, Integer> indexToValue;
    private final Map<Integer, PriorityQueue<Integer>> valueToIndex;

    public NumberContainers() {
        indexToValue = new HashMap<>();
        valueToIndex = new HashMap<>();
    }

    public void change(int index, int number) {
        indexToValue.put(index, number);
        valueToIndex.putIfAbsent(number, new PriorityQueue<>());
        valueToIndex.get(number).offer(index);
    }

    public int find(int number) {
        PriorityQueue<Integer> q = valueToIndex.get(number);
        if (q == null) {
            return -1;
        }
        while (!q.isEmpty() && indexToValue.get(q.peek()) != number) {
            q.poll();
        }
        return q.isEmpty() ? -1 : q.peek();
    }
}

性能