Сложность: 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:
def __init__(self, length: int):
self.snapId = 0
self.historyRecords = [{0: 0} for _ in range(length)]
def set(self, index: int, val: int) -> None:
self.historyRecords[index][self.snapId] = val
def snap(self) -> int:
self.snapId += 1
return self.snapId - 1
def get(self, index: int, snapId: int) -> int:
record = self.historyRecords[index]
while snapId >= 0:
if snapId in record:
return record[snapId]
snapId -= 1
return 0
Ставь 👍 и забирай 📚 Базу знаний