Question

1146. 快照数组

English Version

题目描述

实现支持下列接口的「快照数组」- SnapshotArray：

• SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。
• void set(index, val) - 会将指定索引 index 处的元素设置为 val。
• int snap() - 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。
• int get(index, snap_id) - 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。

 

示例：

输入：["SnapshotArray","set","snap","set","get"]
   [[3],[0,5],[],[0,6],[0,0]]
输出：[null,null,0,null,5]
解释：
SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组
snapshotArr.set(0,5);  // 令 array[0] = 5
snapshotArr.snap();  // 获取快照，返回 snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5

 

提示：

• 1 <= length <= 50000
• 题目最多进行50000 次set，snap，和 get的调用 。
• 0 <= index < length
• 0 <= snap_id < 我们调用 snap() 的总次数
• 0 <= val <= 10^9

解法

方法一：数组 + 二分查找

维护一个数组，数组中的每个元素是一个列表，列表中存储的是每次设置的值以及对应的快照编号。

每次设置值时，将值和快照编号添加到对应索引的列表中。

每次获取值时，使用二分查找，找到对应位置第一个大于快照编号 snap_id 的值，然后返回前一个值即可。

时间复杂度上，设置值的时间复杂度为 $O(1)$，快照的时间复杂度为 $O(1)$，获取值的时间复杂度为 $O(\log n)$。

class SnapshotArray:
  def __init__(self, length: int):
    self.idx = 0
    self.arr = defaultdict(list)

  def set(self, index: int, val: int) -> None:
    self.arr[index].append((self.idx, val))

  def snap(self) -> int:
    self.idx += 1
    return self.idx - 1

  def get(self, index: int, snap_id: int) -> int:
    vals = self.arr[index]
    i = bisect_right(vals, (snap_id, inf)) - 1
    return 0 if i < 0 else vals[i][1]


# Your SnapshotArray object will be instantiated and called as such:
# obj = SnapshotArray(length)
# obj.set(index,val)
# param_2 = obj.snap()
# param_3 = obj.get(index,snap_id)

class SnapshotArray {
  private List<int[]>[] arr;
  private int idx;

  public SnapshotArray(int length) {
    arr = new List[length];
    Arrays.setAll(arr, k -> new ArrayList<>());
  }

  public void set(int index, int val) {
    arr[index].add(new int[] {idx, val});
  }

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

  public int get(int index, int snap_id) {
    var vals = arr[index];
    int left = 0, right = vals.size();
    while (left < right) {
      int mid = (left + right) >> 1;
      if (vals.get(mid)[0] > snap_id) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left == 0 ? 0 : vals.get(left - 1)[1];
  }
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray obj = new SnapshotArray(length);
 * obj.set(index,val);
 * int param_2 = obj.snap();
 * int param_3 = obj.get(index,snap_id);
 */

class SnapshotArray {
public:
  SnapshotArray(int length) {
    idx = 0;
    arr = vector<vector<pair<int, int>>>(length);
  }

  void set(int index, int val) {
    arr[index].push_back({idx, val});
  }

  int snap() {
    return idx++;
  }

  int get(int index, int snap_id) {
    auto& vals = arr[index];
    int left = 0, right = vals.size();
    while (left < right) {
      int mid = (left + right) >> 1;
      if (vals[mid].first > snap_id) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left == 0 ? 0 : vals[left - 1].second;
  }

private:
  vector<vector<pair<int, int>>> arr;
  int idx;
};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */

type SnapshotArray struct {
  idx int
  arr [][]pair
}

func Constructor(length int) SnapshotArray {
  return SnapshotArray{0, make([][]pair, length)}
}

func (this *SnapshotArray) Set(index int, val int) {
  this.arr[index] = append(this.arr[index], pair{this.idx, val})
}

func (this *SnapshotArray) Snap() int {
  this.idx++
  return this.idx - 1
}

func (this *SnapshotArray) Get(index int, snap_id int) int {
  vals := this.arr[index]
  i := sort.Search(len(vals), func(i int) bool { return vals[i].i > snap_id })
  if i == 0 {
    return 0
  }
  return vals[i-1].v
}

type pair struct{ i, v int }

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * obj := Constructor(length);
 * obj.Set(index,val);
 * param_2 := obj.Snap();
 * param_3 := obj.Get(index,snap_id);
 */