[每日一题] 1146.快照数组

Richard

2024 年 04 月 26 日

95 次浏览

暂无评论

2221字数

LeetCode

> https://leetcode.cn/problems/snapshot-array/description/?envType=daily-question&envId=2024-04-11

最开始的想法是记录每一次快照的数组，然后相同的快照指向同一个数组：

```c++
class SnapshotArray {
private:
    int _length, snapIndex;
    int* array;
    std::vector<int*> snappedArray;

public:
    SnapshotArray(int length) : _length(length), snapIndex(-1) {
        array = new int [length + 1];
        memset(array, 0, (length + 1) * sizeof(int));
    }

void set(int index, int val) {
        array[index] = val;
        array[_length] += 1;
    }

int snap() {
        if (snapIndex >= 0 && array[_length] == snappedArray[snapIndex][_length]) {
            snappedArray.push_back(snappedArray[snapIndex]);
        } else {
            int* copy = new int [_length + 1];
            memcpy(copy, array, (_length + 1) * sizeof(int));
            snappedArray.push_back(copy);
        }

return ++snapIndex;
    }

int get(int index, int snap_id) {
        return snappedArray[snap_id][index];
    }
};
```

最坏情况下空间复杂度是 $O(n^2)$ ，$n$ 最大为 $50000$，显然会爆内存。

$set$ 方法只会设置一个位置，所以可以考虑记录每次 $set$ 改变了哪个位置，这样空间复杂度就下降到了 $O(n)$ 。具体实现就是用一个 $length$ 长的数组 $operations$ ，记录每个位置的变化历史以及快照 ID 。

对于 $get$ 方法，因为 $get$ 只需要获取 $index$ 所在位置的值，所以在 $operation[index]$ 中找到小于等于 $snap\_id$ 的值即可。

$snap$ 方法只需要自增一下即可。

```c++
class SnapshotArray {
private:
    int snapIndex;
    std::vector<std::vector<std::pair<int, int>>> operations;

public:
    SnapshotArray(int length) : snapIndex(0) {
        operations.resize(length);
    }

void set(int index, int val) {
        operations[index].emplace_back(snapIndex, val);
    }

int snap() {
        return snapIndex++;
    }

int get(int index, int snap_id) {
        auto res = std::lower_bound(operations[index].rbegin(), operations[index].rend(), std::pair<int, int>(snap_id, -1),
                                    [](std::pair<int, int> element, std::pair<int, int> value) {
                                        return value.first < element.first;
                                    });

if (res == operations[index].rend())
            return 0;

return res->second;
    }
};
```

- 时间复杂度： $set$ 和 $snap$ 方法均为 $O(1)$ ， $get$ 方法为 $O(logn)$ 。
- 空间复杂度：$O(n)$ 。

最后修改：2024 年 05 月 06 日