字节&leetcode1146：快照数组

[sisterAn]

实现支持下列接口的「快照数组」- 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

附赠leetcode地址：leetcode

[sisterAn]

快照，顾名思义，就是对数据进行一次拍照。

对数组进行快照，就是重新创建一个数组，把原来数组的内容拷贝过去，是对数组当前状态的一次记录保存。

事实上，快照是数据存储系统中的一种数据保护技术，主要是实现数据的逻辑保护。所谓逻辑保护，就是当数据出现误删除或者病毒等原因导致数据破坏的情况。通过快照技术，可以将数据恢复到某一个时间点的数据。

解法一：暴力法

每次快照都保存一次数组，但花费的空间复杂度十分高昂的，不实用

解法二：优化，字典数组+二分查找

使用字典数组来记录快照，每次 index 对应的 val 更新时，都把 val 记录到 arr[index].set(this.snapId, val) ，则 arr[index].keys() 为 index 变更的所有记录

但需要查询某次快照的 index 值时，只需知道距离 this.snapId 最近的变更记录既可（ <=this.snapId ）

let SnapshotArray = function(length) {
    // 使用字典数组来记录快照数组
    this.arr = new Array(length).fill(0).map(()=>new Map())
    this.snapId = 0
};

SnapshotArray.prototype.set = function(index, val) {
    this.arr[index].set(this.snapId, val)
};

SnapshotArray.prototype.snap = function() {
    // 快照号是调用 snap() 的总次数减去 1
    this.snapId ++
    return this.snapId - 1
};

SnapshotArray.prototype.get = function(index, snap_id) {
    // 找到这个数的所有记录
    let snapIds = [...this.arr[index].keys()]
    // 二分查找，找到 <= snap_id 的值
    let low = 0, 
        high = snapIds.length - 1,
        mid
    while (low <= high) {
        mid = Math.floor((low+high)/2)
        if (snapIds[mid] < snap_id) {
            low = mid + 1
        } else if (snapIds[mid] > snap_id) {
            high = mid - 1
        } else if (snapIds[mid] === snap_id) {
            return this.arr[index].get(snap_id)
        }
    }
    return this.arr[index].get(snapIds[low-1]) || null
};

leetcode

[Aiyoweioo]

/**
 * @param {number} length
 */
var SnapshotArray = function(length) {
  this.arr = new Array(length)
  for(let i = 0; i < length; i++) {
    this.arr[i] = new Map().set(0, 0) // 使用Map，key是快照id val是数据的值，数组每个元素下的快照id可能不是连续的
  }
  this.snap_id = 0
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
SnapshotArray.prototype.set = function(index, val) {
  let hash = this.arr[index]
  hash.set(this.snap_id, val) //  创建 或者 更新 snap_id的值
};

/**
 * @return {number}
 */
SnapshotArray.prototype.snap = function() {
  return this.snap_id++
};

/** 
 * @param {number} index 
 * @param {number} snap_id
 * @return {number}
 */

SnapshotArray.prototype.get = function(index, snap_id) {
  let map = this.arr[index]
  if(map.has(snap_id)) { // Map查找O(1)
    return this.arr[index].get(snap_id)
  }
  // 找数组中最后一个小于snap_id的索引
  let nums = Array.from(map.keys()) // 取Map按key的插入顺序返回的，因此是升序数组
  // let i  // 从右往左找最后一个小于目标值的索引
  // for(i = nums.length - 1;i >= 0;i--) {
  //   if(nums[i] < snap_id) break;
  // }
  // 二分查找找找最后一个小于目标值的索引
  var find = function(nums, target) {
    let left = 0, right = nums.length - 1
    while (left <= right){
          let mid = Math.floor(left + (right - left)/2);
          if (target <= nums[mid]) {
              right = mid - 1;}
          else {
              left = mid + 1;
          }
      }
      return right >= 0 ? right : 0;
  }
  const i = find(nums, snap_id)
  return map.get(nums[i]) // 索引对应的值就是Map的key
};

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