2349.设计数字容器系统：双哈希表(要咋查就咋映射)

【LetMeFly】2349.设计数字容器系统：双哈希表(要咋查就咋映射)

力扣题目链接：https://leetcode.cn/problems/design-a-number-container-system/

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

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

请你实现一个 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 <= 109
• 调用 change 和 find 的 总次数 不超过 105 次。

解题方法：两个哈希表

核心目标有两个：

1. number查index
2. index改number

所以可以建立两个哈希表映射，一个是index映射为number，一个是number映射为index(s)。

一个index只对应一个number，所以使用int2int就行；一个number可能对应多个index，所以可以使用int2有序集合。

• 时间复杂度$O(\log n)$，其中$n$是表中总数据量
• 空间复杂度$O(n)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-09-17 20:30:45
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-09-17 20:58:14
 */
class NumberContainers {
private:
    unordered_map<int, set<int>> num2idx;
    unordered_map<int, int> idx2num;
public:
    NumberContainers() {
        
    }
    
    void change(int index, int number) {
        auto it = idx2num.find(index);
        if (it != idx2num.end()) {
            int number = (*it).second;
            num2idx[number].erase(index);
        }
        idx2num[index] = number;
        num2idx[number].insert(index);
    }
    
    int find(int number) {
        auto it = num2idx.find(number);
        if (it == num2idx.end() || (*it).second.size() == 0) {
            return -1;
        }
        return *(*it).second.begin();
    }
};

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

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源