Сложность: medium
Реализуйте SnapshotArray, который поддерживает следующий интерфейс:
SnapshotArray(int length) инициализирует структуру данных, похожую на массив, с заданной длиной. Изначально каждый элемент равен 0.
void set(index, val) устанавливает элемент с заданным индексом равным val.
int snap() делает снимок массива и возвращает snap_id: общее количество вызовов snap() минус 1.
int get(index, snap_id) возвращает значение на заданном индексе в момент, когда мы сделали снимок с указанным snap_id.
Пример:
Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation:
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5); // Set array[0] = 5
snapshotArr.snap(); // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0); // Get the value of array[0] with snap_id = 0, return 5
👨💻 Алгоритм:
1⃣Инициализация: Для каждого элемента nums[i] в массиве создайте пустой список для хранения его исторических значений в формате [snap_id, value]. Инициализируйте каждый список, добавив первую запись [0, 0].
2⃣Метод set: Добавьте историческую запись [snap_id, value] в список записей historyRecords[index].
3⃣Методы snap и get:
Метод snap возвращает snap_id и увеличивает его на 1.
Метод get использует бинарный поиск, чтобы найти индекс последней вставки snap_id в данный снимок (целевой индекс будет snap_index - 1). Возвращает historyRecords[index][snap_index - 1][1].
😎 Решение:
class SnapshotArray {
var snapId = 0
var historyRecords: [Int: [Int: Int]]
init(_ length: Int) {
historyRecords = [Int: [Int: Int]]()
for i in 0..<length {
historyRecords[i] = [0: 0]
}
}
func set(_ index: Int, _ val: Int) {
historyRecords[index]![snapId] = val
}
func snap() -> Int {
defer { snapId += 1 }
return snapId
}
func get(_ index: Int, _ snapId: Int) -> Int {
let record = historyRecords[index]!
let keys = Array(record.keys).sorted()
for key in keys.reversed() {
if key <= snapId {
return record[key]!
}
}
return 0
}
}Ставь 👍 и забирай 📚 Базу знаний