Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

https://leetcode.com/problems/snapshot-array/description/
1146. Snapshot Array
設計一個支持快照的陣列，他有以下介面：
SnapshotArray(int length) 初始化陣列大小，預設所有元素為0。
void set(index, val) 設置 陣列[index] = val
int snap() 將當前陣列的狀態保存成一個快照，返回值是快照id，值為快照次數-1。
int get(index, snap_id) 返回該快照id下陣列的值。


Example 1:

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.因為陣列必須保存修改之前的狀態，所以我們在更改和設置陣列的值時，需要帶上版本
  號資訊(快照id)，先將陣列初始化為快照id和值都為0的陣列。

2.set的時候判斷如果index位置的版本和當前相同就直接改，否則插入一個新的版本。

3.get的時候只需要把index的所有版本號拿出來並找出版本和snap_id相同的值即可，如果
  不存在相同的就返回舊的版本(例如：snap_id=5 但是只有4那就返回4)，因為我們在set
  元素的時候必定是按照順序插入的，所以版本號可以用二分搜索去抓出來。

4.snap只要更新快照次數就好。

Java Code：
----------------------------------------------------------
class SnapshotArray {
    private final List<List<int[]>> list;
    private int count;
    public SnapshotArray(int length) {
        list = new ArrayList<>();
        count = 0;
        for (int i = 0; i < length; i++) {
            List<int[]> tmp = new ArrayList<>();
            tmp.add(new int[]{0, 0});
            list.add(tmp);
        }
    }

    public void set(int index, int val) {
        List<int[]> tmp = list.get(index);
        int[] last = tmp.get(tmp.size() - 1);
        if (last[0] == count) {
            last[1] = val;
        } else {
            tmp.add(new int[]{count, val});
        }
    }

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

    public int get(int index, int snap_id) {
        List<int[]> tmp = list.get(index);
        int left = 0;
        int right = tmp.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int id = tmp.get(mid)[0];
            if (id == snap_id) {
                return tmp.get(mid)[1];
            } else if (id > snap_id){
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return tmp.get(left - 1)[1];
    }
}
----------------------------------------------------------

--
https://i.imgur.com/bFRiqA3.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1686491113.A.5CF.html
→ JIWP: 大師
推 wwndbk: 大師
推 Che31128: 大師
→ DDFox: 大師