1146. Snapshot Array

leetcode medium

#array#csharp#hash-table#leetcode#medium#search#sort

Task

Реализуйте 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

C# solution

matched/original

public class SnapshotArray {
    private int snapId = 0;
    private List<SortedDictionary<int, int>> historyRecords;
    
    public SnapshotArray(int length) {
        historyRecords = new List<SortedDictionary<int, int>>(length);
        for (int i = 0; i < length; i++) {
            historyRecords.Add(new SortedDictionary<int, int> { { 0, 0 } });
        }
    }
    public void Set(int index, int val) {
        historyRecords[index][snapId] = val;
    }
    public int Snap() {
        return snapId++;
    }
    public int Get(int index, int snapId) {
        var record = historyRecords[index];
        while (snapId >= 0) {
            if (record.ContainsKey(snapId)) {
                return record[snapId];
            }
            snapId--;
        }
        return 0;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class SnapshotArray {
    private int snapId = 0;
    private List<SortedDictionary<int, int>> historyRecords;
    
    public SnapshotArray(int length) {
        historyRecords = new List<SortedDictionary<int, int>>(length);
        for (int i = 0; i < length; i++) {
            historyRecords.push_back(new SortedDictionary<int, int> { { 0, 0 } });
        }
    }
    public void Set(int index, int val) {
        historyRecords[index][snapId] = val;
    }
    public int Snap() {
        return snapId++;
    }
    public int Get(int index, int snapId) {
        var record = historyRecords[index];
        while (snapId >= 0) {
            if (record.count(snapId)) {
                return record[snapId];
            }
            snapId--;
        }
        return 0;
    }
}

Java solution

matched/original

class SnapshotArray {
    int snapId = 0;
    TreeMap<Integer, Integer>[] historyRecords;
    
    public SnapshotArray(int length) {
        historyRecords = new TreeMap[length];
        for (int i = 0; i < length; i++) {
            historyRecords[i] = new TreeMap<Integer, Integer>();
            historyRecords[i].put(0, 0);
        }
    }

    public void set(int index, int val) {
        historyRecords[index].put(snapId, val);
    }

    public int snap() {
        return snapId++;
    }

    public int get(int index, int snapId) {
        return historyRecords[index].floorEntry(snapId).getValue();
    }
}

JavaScript solution

matched/original

class SnapshotArray {
    constructor(length) {
        this.snapId = 0;
        this.historyRecords = Array.from({ length }, () => new Map([[0, 0]]));
    }

    set(index, val) {
        this.historyRecords[index].set(this.snapId, val);
    }

    snap() {
        return this.snapId++;
    }

    get(index, snapId) {
        const record = this.historyRecords[index];
        while (snapId >= 0) {
            if (record.has(snapId)) {
                return record.get(snapId);
            }
            snapId--;
        }
        return 0;
    }
}

Python solution

matched/original

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

Go solution

matched/original

type SnapshotArray struct {
    snapId         int
    historyRecords []map[int]int
}

func Constructor(length int) SnapshotArray {
    historyRecords := make([]map[int]int, length)
    for i := range historyRecords {
        historyRecords[i] = map[int]int{0: 0}
    }
    return SnapshotArray{0, historyRecords}
}

func (this *SnapshotArray) Set(index int, val int) {
    this.historyRecords[index][this.snapId] = val
}

func (this *SnapshotArray) Snap() int {
    this.snapId++
    return this.snapId - 1
}

func (this *SnapshotArray) Get(index int, snapId int) int {
    record := this.historyRecords[index]
    for s := snapId; s >= 0; s-- {
        if val, ok := record[s]; ok {
            return val
        }
    }
    return 0
}

Explanation

Algorithm

Инициализация: Для каждого элемента nums[i] в массиве создайте пустой список для хранения его исторических значений в формате [snap_id, value]. Инициализируйте каждый список, добавив первую запись [0, 0].

Метод set: Добавьте историческую запись [snap_id, value] в список записей historyRecords[index].

Методы snap и get:

Метод snap возвращает snap_id и увеличивает его на 1.

Метод get использует бинарный поиск, чтобы найти индекс последней вставки snap_id в данный снимок (целевой индекс будет snap_index - 1). Возвращает historyRecords[index][snap_index - 1][1].

😎