2349. 设计数字容器系统

Medium

题目描述

设计一个数字容器系统，能够执行以下操作：

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

实现 NumberContainers 类：

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

示例 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 次。

解题思路

这道题需要设计一个支持动态更新和查询的数据结构。核心思路是使用两个哈希表来维护映射关系：

数据结构设计：

indexToNumber：记录每个索引位置当前存储的数字
numberToIndices：记录每个数字对应的所有索引集合，使用有序集合（如 set）来快速获取最小索引

操作实现：

change(index, number)：首先检查该索引是否已有数字，如果有则从旧数字的索引集合中移除该索引；然后将新的映射关系添加到两个哈希表中
find(number)：直接查询 numberToIndices 中该数字的最小索引，有序集合的第一个元素就是答案

关键优化点： 使用有序集合（如 C++ 的 set、Python 的 SortedSet 或手动维护最小堆）来存储每个数字对应的索引，这样可以在 O(log n) 时间内完成插入、删除和查询最小值操作。

时间复杂度方面，每次 change 操作需要 O(log n)，find 操作需要 O(1) 或 O(log n)（取决于实现），整体效率很高。

代码实现

class NumberContainers {
private:
    unordered_map<int, int> indexToNumber;
    unordered_map<int, set<int>> numberToIndices;
    
public:
    NumberContainers() {
        
    }
    
    void change(int index, int number) {
        // 如果索引已有数字，先从旧数字的集合中移除
        if (indexToNumber.find(index) != indexToNumber.end()) {
            int oldNumber = indexToNumber[index];
            numberToIndices[oldNumber].erase(index);
            if (numberToIndices[oldNumber].empty()) {
                numberToIndices.erase(oldNumber);
            }
        }
        
        // 更新映射关系
        indexToNumber[index] = number;
        numberToIndices[number].insert(index);
    }
    
    int find(int number) {
        if (numberToIndices.find(number) == numberToIndices.end() || 
            numberToIndices[number].empty()) {
            return -1;
        }
        return *numberToIndices[number].begin();
    }
};

from sortedcontainers import SortedSet

class NumberContainers:

    def __init__(self):
        self.index_to_number = {}
        self.number_to_indices = {}

    def change(self, index: int, number: int) -> None:
        # 如果索引已有数字，先从旧数字的集合中移除
        if index in self.index_to_number:
            old_number = self.index_to_number[index]
            self.number_to_indices[old_number].remove(index)
            if not self.number_to_indices[old_number]:
                del self.number_to_indices[old_number]
        
        # 更新映射关系
        self.index_to_number[index] = number
        if number not in self.number_to_indices:
            self.number_to_indices[number] = SortedSet()
        self.number_to_indices[number].add(index)

    def find(self, number: int) -> int:
        if number not in self.number_to_indices or not self.number_to_indices[number]:
            return -1
        return self.number_to_indices[number][0]

public class NumberContainers {
    private Dictionary<int, int> indexToNumber;
    private Dictionary<int, SortedSet<int>> numberToIndices;

    public NumberContainers() {
        indexToNumber = new Dictionary<int, int>();
        numberToIndices = new Dictionary<int, SortedSet<int>>();
    }
    
    public void Change(int index, int number) {
        // 如果索引已有数字，先从旧数字的集合中移除
        if (indexToNumber.ContainsKey(index)) {
            int oldNumber = indexToNumber[index];
            numberToIndices[oldNumber].Remove(index);
            if (numberToIndices[oldNumber].Count == 0) {
                numberToIndices.Remove(oldNumber);
            }
        }
        
        // 更新映射关系
        indexToNumber[index] = number;
        if (!numberToIndices.ContainsKey(number)) {
            numberToIndices[number] = new SortedSet<int>();
        }
        numberToIndices[number].Add(index);
    }
    
    public int Find(int number) {
        if (!numberToIndices.ContainsKey(number) || numberToIndices[number].Count == 0) {
            return -1;
        }
        return numberToIndices[number].Min;
    }
}

var NumberContainers = function() {
    this.indexToNumber = new Map();
    this.numberToIndices = new Map();
};

NumberContainers.prototype.change = function(index, number) {
    if (this.indexToNumber.has(index)) {
        const oldNumber = this.indexToNumber.get(index);
        const indices = this.numberToIndices.get(oldNumber);
        indices.delete(index);
        if (indices.size === 0) {
            this.numberToIndices.delete(oldNumber);
        }
    }
    
    this.indexToNumber.set(index, number);
    
    if (!this.numberToIndices.has(number)) {
        this.numberToIndices.set(number, new Set());
    }
    this.numberToIndices.get(number).add(index);
};

NumberContainers.prototype.find = function(number) {
    if (!this.numberToIndices.has(number)) {
        return -1;
    }
    
    const indices = this.numberToIndices.get(number);
    return Math.min(...indices);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
change	O(log n)	O(1)
find	O(1) - O(log n)*	O(1)
总空间	-	O(n)

*注：find 操作在 C++/C# 中是 O(1)，在 Python 中使用 SortedSet 是 O(1)，在 JavaScript 中需要遍历 Set 所以是 O(n)，但可以优化为 O(log n)。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目