2349. 设计数字容器系统
设计一个数字容器系统，可以实现以下功能：
请你实现一个 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 <= 109change 和 find 的 总次数 不超过 105 次。原站题解
python3 解法, 执行用时: 1444 ms, 内存消耗: 154.1 MB, 提交时间: 2023-09-23 11:09:49
from sortedcontainers import SortedSet
class NumberContainers:
def __init__(self):
self.m = {}
self.ms = defaultdict(SortedSet)
def change(self, index: int, number: int) -> None:
if index in self.m:
self.ms[self.m[index]].remove(index) # 移除旧数据
self.m[index] = number
self.ms[number].add(index) # 添加新数据
def find(self, number: int) -> int:
s = self.ms[number]
return s[0] if s else -1
class NumberContainers2:
def __init__(self):
self.m = {}
self.ms = defaultdict(list)
def change(self, index: int, number: int) -> None:
self.m[index] = number
heappush(self.ms[number], index) # 直接添加新数据，后面 find 再删除旧的
def find(self, number: int) -> int:
h = self.ms[number]
while h and self.m[h[0]] != number: # 意味着 h[0] 处的元素已被替换成了其他值
heappop(h)
return h[0] if h else -1
# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)
java 解法, 执行用时: 82 ms, 内存消耗: 93.2 MB, 提交时间: 2023-09-23 11:09:22
class NumberContainers {
Map<Integer, Integer> m = new HashMap<>();
Map<Integer, TreeSet<Integer>> ms = new HashMap<>();
public void change(int index, int number) {
var old = m.get(index);
if (old != null) ms.get(old).remove(index); // 移除旧数据
m.put(index, number);
ms.computeIfAbsent(number, k -> new TreeSet<>()).add(index); // 添加新数据
}
public int find(int number) {
var s = ms.get(number);
return s == null || s.isEmpty() ? -1 : s.first();
}
}
// 堆
class NumberContainers2 {
Map<Integer, Integer> m = new HashMap<>();
Map<Integer, Queue<Integer>> ms = new HashMap<>();
public void change(int index, int number) {
m.put(index, number);
ms.computeIfAbsent(number, k -> new PriorityQueue<>()).offer(index); // 直接添加新数据，后面 find 再删除旧的
}
public int find(int number) {
var q = ms.get(number);
if (q == null) return -1;
while (!q.isEmpty() && m.get(q.peek()) != number) q.poll();
return q.isEmpty() ? -1 : q.peek();
}
}
/**
* Your NumberContainers object will be instantiated and called as such:
* NumberContainers obj = new NumberContainers();
* obj.change(index,number);
* int param_2 = obj.find(number);
*/
cpp 解法, 执行用时: 472 ms, 内存消耗: 183.9 MB, 提交时间: 2023-09-23 11:08:45
class NumberContainers {
unordered_map<int, int> m;
unordered_map<int, set<int>> ms;
public:
void change(int index, int number) {
auto it = m.find(index);
if (it != m.end()) {
ms[it->second].erase(index); // 移除旧数据
it->second = number; // 优化：直接在迭代器上赋值
} else m[index] = number;
ms[number].insert(index); // 添加新数据
}
int find(int number) {
auto it = ms.find(number);
return it == ms.end() || it->second.empty() ? -1 : *it->second.begin();
}
};
// 懒删除堆
class NumberContainers2 {
unordered_map<int, int> m;
unordered_map<int, priority_queue<int, vector<int>, greater<>>> ms;
public:
void change(int index, int number) {
m[index] = number;
ms[number].push(index); // 直接添加新数据，后面 find 再删除旧的
}
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();
}
};
/**
* Your NumberContainers object will be instantiated and called as such:
* NumberContainers* obj = new NumberContainers();
* obj->change(index,number);
* int param_2 = obj->find(number);
*/
golang 解法, 执行用时: 456 ms, 内存消耗: 47.3 MB, 提交时间: 2023-09-23 11:07:51
type NumberContainers struct {
m map[int]int
ms map[int]*hp
}
func Constructor() NumberContainers {
return NumberContainers{map[int]int{}, map[int]*hp{}}
}
func (n NumberContainers) Change(index int, number int) {
n.m[index] = number
if n.ms[number] == nil {
n.ms[number] = &hp{}
}
heap.Push(n.ms[number], index) // 直接添加新数据，后面 find 再删除旧的
}
func (n NumberContainers) Find(number int) int {
h, ok := n.ms[number]
if !ok {
return -1
}
for h.Len() > 0 && n.m[h.IntSlice[0]] != number {
heap.Pop(h)
}
if h.Len() == 0 {
return -1
}
return h.IntSlice[0]
}
type hp struct{ sort.IntSlice }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }
/**
* Your NumberContainers object will be instantiated and called as such:
* obj := Constructor();
* obj.Change(index,number);
* param_2 := obj.Find(number);
*/
golang 解法, 执行用时: 476 ms, 内存消耗: 57.4 MB, 提交时间: 2023-09-23 11:07:29
// 平衡树
type NumberContainers struct {
m map[int]int
ms map[int]*redblacktree.Tree
}
func Constructor() NumberContainers {
return NumberContainers{map[int]int{}, map[int]*redblacktree.Tree{}}
}
func (n NumberContainers) Change(index int, number int) {
if num, ok := n.m[index]; ok {
n.ms[num].Remove(index) // 移除旧数据
}
n.m[index] = number
if n.ms[number] == nil {
n.ms[number] = redblacktree.NewWithIntComparator()
}
n.ms[number].Put(index, nil) // 添加新数据
}
func (n NumberContainers) Find(number int) int {
s, ok := n.ms[number]
if !ok || s.Size() == 0 {
return -1
}
return s.Left().Key.(int)
}
/**
* Your NumberContainers object will be instantiated and called as such:
* obj := Constructor();
* obj.Change(index,number);
* param_2 := obj.Find(number);
*/