力扣1146 快照数组

思路:初始时,使用的思路是对于每个快照的数组都进行一次副本保存,但是提交后是时间超出。因此基于 灵神. - 力扣(LeetCode) 的思路不构建数组,而是保存每个数组位置set的记录,记录采用的是键值对的形式,键为当前快照号,值为传递过来需要修改的val;这样构造函数、set以及snap方法都可以比较精简的得到解决。

对于get方法,若没有构建数组存储每个时刻的数据而是直接记录版本更新情况的话,在二分查找时所检索的不是等于当前snap_id的记录,而是需要找到索引list中小于snap_id的第一个元素(因为同一个index出,可以有多个快照号相同的记录);因此二分查找使用红蓝染色法,返回left。

class SnapshotArray {
    // 快照编号
    int snapidx;
    Map<Integer, List<int[]>> map = new HashMap<>();

    public SnapshotArray(int length) {
        // 定位快照编号
        snapidx = 0;
        // arr = new int[length];
        // 构建map,提前为每个索引建立好历史记录列表
        for(int i=0; i<length; i++){
            List<int[]> list = new ArrayList<>();
            map.put(i, list);
        }
    }
    
    public void set(int index, int val) {
        // 当前版本的数据更新
        // arr[index] = val;
        // 增加一条记录
        List<int[]> list = map.get(index);
        list.add(new int[]{snapidx, val});  // list内加入的元素总是按照时间的先后往其中加入的
        map.put(index, list);
    }
    
    public int snap() {
        snapidx++;
        return snapidx-1;
    }
    
    public int get(int index, int snap_id) {
        // 获取到当前的索引位置的历史版本
        List<int[]> list = map.get(index);
        // 本质上可以通过遍历来实现,使用二分查找加快查找的速度
        int idx = binarysearch(list, snap_id);
        return idx<0? 0:list.get(idx)[1];
    }

    public int binarysearch(List<int[]> list, int snapid){
        // 红蓝染色法的二分查找
        int left = -1;
        int right = list.size();
        while(left + 1 != right){
            int mid = left + (right-left)/2;
            if(list.get(mid)[0] <= snapid)
                left = mid;
            else
                right = mid;
        }

        return left;

    }
}

/**
 * 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);
 */

相关推荐

  1. 1146 快照数组

    2024-04-29 17:48:02       40 阅读
  2. 1146.快照数组

    2024-04-29 17:48:02       32 阅读
  3. leetcode1146--快照数组

    2024-04-29 17:48:02       38 阅读
  4. LeetCode 每日一题 ---- 【1146.快照数组

    2024-04-29 17:48:02       37 阅读
  5. 100】146.LRU缓存

    2024-04-29 17:48:02       70 阅读
  6. 记录)146. LRU 缓存

    2024-04-29 17:48:02       56 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-29 17:48:02       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-29 17:48:02       101 阅读
  3. 在Django里面运行非项目文件

    2024-04-29 17:48:02       82 阅读
  4. Python语言-面向对象

    2024-04-29 17:48:02       91 阅读

热门阅读

  1. LINUX 系统编程 局域网聊天室项目

    2024-04-29 17:48:02       29 阅读
  2. 抖音运营必备:作品发布必知的6大注意事项!

    2024-04-29 17:48:02       32 阅读
  3. Python中的map()和filter()函数:深入解析与使用场景

    2024-04-29 17:48:02       128 阅读
  4. python打印金字塔

    2024-04-29 17:48:02       134 阅读
  5. AI智能体的未来:引领科技创新潮流

    2024-04-29 17:48:02       27 阅读
  6. Support contact(DayMatter App)

    2024-04-29 17:48:02       37 阅读
  7. 同步与异步

    2024-04-29 17:48:02       36 阅读
  8. C#算法之希尔排序

    2024-04-29 17:48:02       39 阅读
  9. Kotlin->Kotlin协程作用域

    2024-04-29 17:48:02       29 阅读
  10. vite: 项目中使用Sass

    2024-04-29 17:48:02       28 阅读
  11. 通过iptables限制docker 容器的运行端口

    2024-04-29 17:48:02       36 阅读