Posted on 2023-06-11 18:12
Uriel 閱讀(78)
評論(0) 編輯 收藏 引用 所屬分類:
模擬 、
閑來無事重切Leet Code 、
二分.三分
模擬一個支持不斷做snapshot并且可以查詢第i次snapshot時數組某個index的數值，數組中的所有數值都支持無限次set，并且由于memory限制，不能直接存儲每一次snapshot的數組所有元素
參考了Discussion思路->https://leetcode.com/problems/snapshot-array/solutions/3623538/simple-java-c-python-easy-to-understand/
1 #1146
2 #Runtime: 706 ms (Beats 30.51%)
3 #Memory: 45.6 MB (Beats 66.10%)
4
5 class SnapshotArray(object):
6
7 def __init__(self, length):
8 """
9 :type length: int
10 """
11 self.cur_arr = [0] * length
12 self.his_arr = [[0] for _ in range(length)]
13 self.modifed_idx_list = set()
14 self.snap_id = 0
15 self.snap_id_arr = [[-1] for _ in range(length)]
16
17
18 def set(self, index, val):
19 """
20 :type index: int
21 :type val: int
22 :rtype: None
23 """
24 if self.his_arr[index][-1] == val:
25 if index in self.modifed_idx_list:
26 self.modifed_idx_list.remove(index)
27 return
28 self.cur_arr[index] = val
29 if index not in self.modifed_idx_list:
30 self.modifed_idx_list.add(index)
31
32
33 def snap(self):
34 """
35 :rtype: int
36 """
37 for i in self.modifed_idx_list:
38 self.snap_id_arr[i].append(self.snap_id)
39 self.his_arr[i].append(self.cur_arr[i])
40 self.modifed_idx_list.clear()
41 self.snap_id += 1
42 return self.snap_id - 1
43
44
45 def get(self, index, snap_id):
46 """
47 :type index: int
48 :type snap_id: int
49 :rtype: int
50 """
51 arr = self.snap_id_arr[index]
52 l, r = 1, len(arr)
53 while l < r:
54 mid = (l + r) // 2
55 if arr[mid] <= snap_id:
56 l = mid + 1
57 else:
58 r = mid
59 return self.his_arr[index][l - 1]
60
61
62
63 # Your SnapshotArray object will be instantiated and called as such:
64 # obj = SnapshotArray(length)
65 # obj.set(index,val)
66 # param_2 = obj.snap()
67 # param_3 = obj.get(index,snap_id)