2349. 设计数字容器系统

🟠   🔖  设计 哈希表 有序集合 堆（优先队列）  🔗 力扣 LeetCode

题目

Design a number container system that can do the following:

• Insert or Replace a number at the given index in the system.
• Return the smallest index for the given number in the system.

Implement the NumberContainers class:

• NumberContainers() Initializes the number container system.
• void change(int index, int number) Fills the container at index with the number. If there is already a number at that index, replace it.
• int find(int number) Returns the smallest index for the given number, or -1 if there is no index that is filled by number in the system.

Example 1:

Input

["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]

[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]

Output

[null, -1, null, null, null, null, 1, null, 2]

Explanation

NumberContainers nc = new NumberContainers();

nc.find(10); // There is no index that is filled with number 10. Therefore, we return -1.

nc.change(2, 10); // Your container at index 2 will be filled with number 10.

nc.change(1, 10); // Your container at index 1 will be filled with number 10.

nc.change(3, 10); // Your container at index 3 will be filled with number 10.

nc.change(5, 10); // Your container at index 5 will be filled with number 10.

nc.find(10); // Number 10 is at the indices 1, 2, 3, and 5. Since the smallest index that is filled with 10 is 1, we return 1.

nc.change(1, 20); // Your container at index 1 will be filled with number 20. Note that index 1 was filled with 10 and then replaced with 20.

nc.find(10); // Number 10 is at the indices 2, 3, and 5. The smallest index that is filled with 10 is 2. Therefore, we return 2.

Constraints:

• 1 <= index, number <= 10^9
• At most 10^5 calls will be made in total to change and find.

题目大意

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

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

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

解题思路

1. 双向映射存储

   • indexMap：用于记录每个索引对应的数值。
   • numberMap：每个数值维护一个最小堆（MinHeap），存储该数值对应的索引。

2. 堆维护最小索引

   • 使用 MinHeap 来高效管理每个数值的索引，并支持快速获取最小索引。

3. 堆清理优化

   • 由于数值变化可能导致堆中存储的索引无效，需要在 find() 操作中动态清理堆顶无效索引。

4. 代码逻辑详解

• change(index, number)

  • 若索引的数值未发生变化直接返回。
  • 如果索引原本存在旧值，将该旧值的索引标记为无效。
  • 将新的数值插入 numberMap 中的堆。

• find(number)

  • 若 number 不存在或其堆为空，返回 -1。
  • 清理堆中无效的索引，直到堆顶为有效索引或堆为空。
  • 返回最小有效索引。

• MinHeap 实现

  • insert()：插入新索引并上浮调整堆。
  • pop()：弹出堆顶元素并下沉调整堆。
  • top()：获取堆顶元素。

复杂度分析

• 时间复杂度
  • change()：O(log n)，插入或删除堆元素的时间复杂度。
  • find()：最坏情况下 O(log n)，需要清理无效索引。
• 空间复杂度：O(n)，存储所有索引及数值对应关系的空间。

代码

var NumberContainers = function () {
	this.indexMap = new Map();
	this.numberMap = new Map();
};

/**
 * @param {number} index
 * @param {number} number
 * @return {void}
 */
NumberContainers.prototype.change = function (index, number) {
	if (this.indexMap.get(index) == number) return;
	this.indexMap.set(index, number);
	if (!this.numberMap.has(number)) {
		this.numberMap.set(number, new MinHeap());
	}
	this.numberMap.get(number).insert(index);
};

/**
 * @param {number} number
 * @return {number}
 */
NumberContainers.prototype.find = function (number) {
	if (!this.numberMap.has(number) || this.numberMap.get(number).size() == 0) {
		return -1;
	}
	let heap = this.numberMap.get(number);
	while (heap.size() > 0 && this.indexMap.get(heap.top()) !== number) {
		heap.pop();
	}
	return heap.size() == 0 ? -1 : heap.top();
};

class MinHeap {
	constructor() {
		this.heap = [];
	}
	insert(num) {
		this.heap.push(num);
		this.heapifyUp(this.heap.length - 1);
	}
	pop() {
		if (this.heap.length == 0) return null;
		const top = this.heap[0];
		const last = this.heap.pop();
		if (this.heap.length) {
			this.heap[0] = last;
			this.heapifyDown(0);
		}
		return top;
	}
	top() {
		return this.heap[0];
	}
	size() {
		return this.heap.length;
	}
	heapifyUp(i) {
		while (i) {
			const parent = ((i - 1) / 2) | 0;
			if (this.heap[parent] > this.heap[i]) {
				[this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
				i = parent;
			} else {
				break;
			}
		}
	}
	heapifyDown(i) {
		let left = i * 2 + 1,
			right = i * 2 + 2,
			min = i;
		if (left < this.heap.length && this.heap[left] < this.heap[min]) {
			min = left;
		}
		if (right < this.heap.length && this.heap[right] < this.heap[min]) {
			min = right;
		}
		if (min !== i) {
			[this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]];
			this.heapifyDown(min);
		}
	}
}
/**
 * Your NumberContainers object will be instantiated and called as such:
 * var obj = new NumberContainers()
 * obj.change(index,number)
 * var param_2 = obj.find(number)
 */

相关题目

题号	标题	题解	标签	难度	力扣
1845	座位预约管理系统		设计 堆（优先队列）	🟠	🀄️ 🔗
2353	设计食物评分系统		设计 哈希表 有序集合 1+	🟠	🀄️ 🔗