LeetCode 1146 二分查找

发表于

思路：

数组保存所有数。同时，每个set只记录增量，通过二分查找得到最近snap的数。

关键点，对于没有set的数，即使snap了，也和上一个snap_id是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 这里之所以要用float('inf')的原因是，这样当出现第一项相同时，必然往后靠
import bisect

class SnapshotArray:

    def __init__(self, length: int):
        self.snaps = [[[-1,0]] for i in range(length)]
        self.snap_id = 0

    def set(self, index: int, val: int) -> None:
        self.snaps[index].append([self.snap_id,val])
        
    def snap(self) -> int:
        self.snap_id+=1
        return self.snap_id-1

    def get(self, index: int, snap_id: int) -> int:
        idx = bisect.bisect_right(self.snaps[index],[snap_id,float('inf')])-1
        return self.snaps[index][idx][1]