981. 基于时间的键值存储

题目描述

设计一个类 TimeMap，同一个键可以在不同时间戳下保存不同的值，并能按时间戳查询。

TimeMap()：创建一个空的结构。

set(key, value, timestamp)：记录在时间戳 timestamp 时，键 key 对应的值为 value。无返回值。

get(key, timestamp)：在 key 的所有记录中，找出时间戳不超过 timestamp 的那些，返回其中时间戳最大的那条记录的值。若没有这样的记录，返回空串 ""。

示例 1

输入：操作 = ["TimeMap","set","get","get","set","get","get"]
参数 = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
输出：[null,null,"bar","bar",null,"bar2","bar2"]

解释：时刻 1 存入 bar，查询 1 和 3 都得到 bar；时刻 4 存入 bar2 后，查询 4 和 5 得到 bar2。

数据范围

1 <= key.length, value.length <= 100
key 和 value 只含小写英文字母和数字。
1 <= timestamp <= 10^7
所有 set 调用的 timestamp 严格递增。
set 和 get 总共最多调用 2 * 10^5 次。

解题思路

每个 key 对应一个 (时间戳, 值) 列表。因为时间戳严格递增，直接追加就天然有序。get 时在列表上二分，找第一个时间戳 > timestamp 的位置 lo（即 bisect_right），答案就是它前一个元素 h[lo-1]；如果 lo = 0，说明所有记录都晚于 timestamp，返回空串。

为什么正确

二分过程中，下标 < lo 的记录时间戳都 ≤ timestamp，下标 ≥ hi 的都 > timestamp。

复杂度分析

set O(1)，get O(log m)（m 是该 key 的记录数）；空间 O(set 次数)。

易错点

要找的是“最后一个 ≤ timestamp”，用 bisect_left 会在时间戳刚好相等时取到前一条；还要处理 key 不存在和 timestamp 早于第一条记录两种返回空串的情况。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class TimeMap:
    def __init__(self):
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = []
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        h = self.store.get(key, [])
        lo, hi = 0, len(h)
        while lo < hi:
            mid = (lo + hi) // 2
            if h[mid][0] <= timestamp:
                lo = mid + 1
            else:
                hi = mid
        if lo == 0:
            return ""
        return h[lo - 1][1]

class TimeMap {
    private Map<String, List<Object[]>> store;

    public TimeMap() {
        store = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        if (!store.containsKey(key)) {
            store.put(key, new ArrayList<>());
        }
        store.get(key).add(new Object[]{timestamp, value});
    }

    public String get(String key, int timestamp) {
        List<Object[]> h = store.getOrDefault(key, new ArrayList<>());
        int lo = 0, hi = h.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if ((int) h.get(mid)[0] <= timestamp) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        if (lo == 0) {
            return "";
        }
        return (String) h.get(lo - 1)[1];
    }
}

class TimeMap {
public:
    unordered_map<string, vector<pair<int, string>>> store;

    TimeMap() {
        store.clear();
    }

    void set(string key, string value, int timestamp) {
        store[key].push_back({timestamp, value});
    }

    string get(string key, int timestamp) {
        auto it = store.find(key);
        if (it == store.end()) {
            return "";
        }
        auto& h = it->second;
        int lo = 0, hi = h.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (h[mid].first <= timestamp) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        if (lo == 0) {
            return "";
        }
        return h[lo - 1].second;
    }
};

type entry struct {
	ts  int
	val string
}

type TimeMap struct {
	store map[string][]entry
}

func Constructor() TimeMap {
	return TimeMap{store: map[string][]entry{}}
}

func (this *TimeMap) Set(key string, value string, timestamp int) {
	if _, ok := this.store[key]; !ok {
		this.store[key] = []entry{}
	}
	this.store[key] = append(this.store[key], entry{timestamp, value})
}

func (this *TimeMap) Get(key string, timestamp int) string {
	h := this.store[key]
	lo, hi := 0, len(h)
	for lo < hi {
		mid := (lo + hi) / 2
		if h[mid].ts <= timestamp {
			lo = mid + 1
		} else {
			hi = mid
		}
	}
	if lo == 0 {
		return ""
	}
	return h[lo-1].val
}

class TimeMap {
    constructor() {
        this.store = new Map();
    }

    set(key, value, timestamp) {
        if (!this.store.has(key)) {
            this.store.set(key, []);
        }
        this.store.get(key).push([timestamp, value]);
    }

    get(key, timestamp) {
        const h = this.store.get(key) || [];
        let lo = 0, hi = h.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (h[mid][0] <= timestamp) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        if (lo === 0) {
            return "";
        }
        return h[lo - 1][1];
    }
}

class TimeMap {
    store: Map<string, [number, string][]>;

    constructor() {
        this.store = new Map();
    }

    set(key: string, value: string, timestamp: number): void {
        if (!this.store.has(key)) {
            this.store.set(key, []);
        }
        this.store.get(key)!.push([timestamp, value]);
    }

    get(key: string, timestamp: number): string {
        const h = this.store.get(key) || [];
        let lo = 0, hi = h.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (h[mid][0] <= timestamp) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        if (lo === 0) {
            return "";
        }
        return h[lo - 1][1];
    }
}

载入编辑器，自己跑一遍 →

设计专题的其他题目

查看设计全部题目 →