Re: [閒聊] 每日LeetCode

[pandix (麵包屌)]

※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: 981. Time Based Key-Value Store
: 設計一個資料結構，這個資料結構儲存key/value值，他可以接受相同key不同時間
: 儲存不同value，實作以下功能：
: 1.TimeMap()
: 建構函數。
: 2.void set(String key, String value, int timestamp)
: 設定一個key/value鍵值對，且包含時間資訊。
: 3.String get(String key, int timestamp)
: 透過key獲得一個value值，若有多個value，向下取離timestamp最近的，
: 若不存在key返回""
: 限制：
: 所有輸入的timestamp都是嚴格遞增
: Example 1:
: Input
: ["TimeMap", "set", "get", "get", "set", "get", "get"]
: [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo",
: 4], ["foo", 5]]
: Output
: [null, null, "bar", "bar", null, "bar2", "bar2"]

因為要找最近的 timestamp,  map[key] 最好要是 sorted list

這樣 get 的時候在 map[key] 這個 list 裡二分搜就好

因為輸入有限制嚴格遞增所以 set 的時候直接 append 就好 不用再 bisect.insort

class TimeMap:

    def __init__(self):
        self.map = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.map[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        idx = bisect.bisect_right(self.map[key], timestamp, key = lambda x:
x[0])-1
        return self.map[key][idx][1] if idx >= 0 else ''


get 的時候因為 timestamp 最小導致 idx 拿到 -1 的時候要額外處理


--

蛤?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.199.166 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1665023274.A.456.html
推 Rushia: 對ㄟ好像不用排序 已經排好了  大師
噓 MikuLover: 講中文
→ qwer338859: (timestamp, value)拍森的list有key/value喔
→ pandix: 啊啊 那是tuple 在排序的時候才能用x[0]當排序的key
→ pandix: x[1]當實際要回傳的value
→ Rushia: JAVA好像沒內建TUPLE= =
→ Rushia: map也不能二分搜尋 太苦了
→ pandix: 太苦了== 我已經被bisect寵壞了