当前位置：首页 > article >正文

【懒删除堆】力扣2349. 设计数字容器系统

article 2025/2/1 4:17:25

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

在系统中给定下标处插入或者替换一个数字。
返回系统中给定数字的最小下标。
请你实现一个 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 。

在这里插入图片描述

懒删除堆

class NumberContainers {
    unordered_map<int, int> m;
    unordered_map<int, priority_queue<int, vector<int>, greater<int>>> ms;
public:
    NumberContainers() {
        
    }
    
    void change(int index, int number) {
        m[index] = number;
        ms[number].push(index);
    }
    
    int find(int number) {
        auto it = ms.find(number);
        if(it == ms.end()) return -1;
        auto &q = it -> second;
        while(!q.empty() && m[q.top()] != number) q.pop();
        return q.empty() ? -1 : q.top();
    }
};

我们可以建立一个哈希表m用来储存最新的index存放的是哪个number。我们再建立一个哈希表ms，键用来储存number，然后值用一个最小堆来储存index。最小堆实际上就是我们需要的最小索引，但是由于可能最小堆里的数值的索引可能被替换掉，所以我们要进行检查。当m[q.top()] != number的时候，说明该索引已经被替换成其他值，所以我们就将最小堆堆顶元素弹出，最后满足m[q.top()] = number的堆顶元素就是代码中构造的find函数的返回值。

查看全文

http://www.kler.cn/a/526700.html