1146. Snapshot Array PHP解題

更新於 分類於 閱讀次數：

題目說明

Implement a SnapshotArray that supports the following interface:

  • SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.
  • void set(index, val) sets the element at the given index to be equal to val.
  • int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
  • int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Input / Output(測試資料輸入/輸出):

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

Constraints(參數限制):

  • 1 <= length <= 5 * 104
  • 0 <= index < length
  • 0 <= val <= 109
  • 0 <= snap_id < (the total number of times we call snap())
    At most 5 * 104 calls will be made to set, snap, and get.

解題思路

要做出一個可以快照目前陣列內容的功能，以下就個別功能說明

SnapshotArray(int length)

初始化陣列，length 會等於 陣列總長度，初始陣列為全部 0。

set(index, val)

依照輸入的 val 來設置 陣列[index] 的數值

snap()

對目前資料陣列進行快照動作，回傳數值為 目前快照次數 - 1;

get(index, snap_id)

取得目前在 snap_id 下該陣列[index] 的數值

此題目的測試範圍不小，且有記憶體限制，記錄太多東西執行上就會超時，
那節省記憶體的陣列做法是將資料存成二維陣列，資料除了設置的數值外多存一個快照ID，取資料的時候會用到(快照ID=snap_id)，此時將對應的陣列[index]傳進去，利用二分搜尋法查詢 符合條件的snap_id數值就能找到資料了！

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class SnapshotArray {
    /**
     * @param Integer $length
     */
    function __construct($length) {
        $this->snap_c = 0;
        for($i=0;$i<$length;$i++){
            $this->snap_array[$i][] = [0,0];
        }
    }
  
    /**
     * @param Integer $index
     * @param Integer $val
     * @return NULL
     */
    function set($index, $val) { 
        $this->snap_array[$index][] = [$this->snap_c,$val];  
    }
  
    /**
     * @return Integer
     */
    function snap() {
       return $this->snap_c++;
    }
  
    /**
     * @param Integer $index
     * @param Integer $snap_id
     * @return Integer
     */
    function get($index, $snap_id) {
       return $this->getData($this->snap_array[$index],$snap_id)[1];
       
    }
    private function getData($arr,$target){
        $max = count($arr);
        $min = 0;
        while($min < $max){
            $mid = $min + floor( ($max - $min ) /2);
            if($arr[$mid][0] <= $target){
                $min = $mid + 1;
            }else{
                $max = $mid;
            }
        }
        return $arr[$min-1];
    }
}