981. Time Based Key-Value Store - Medium

前往題目

之前的文章

想法

• Hashmap儲存鍵值對，重點是如何根據timestamp取得同一個或是最相近timestamp的key呢
• 題目說timestamp和set都是嚴格遞增的，所以不會出現重複的時間戳，那是不是可以組timestamp -> value

思路

大致上有兩種做法

• 使用Pair
• 使用TreeMap

這裡使用pair，舊的那篇兩個方法都有寫

1. 利用Hashmap儲存key與value的關係，其中value要使用list<pair<>>來儲存，也就是pair裡面儲存的是value與timestamp的組合，至於會有幾種組合不知道所以用list，ArrayList實作
2. set方法很簡單，把資料放進map就好
3. get則是利用binary search在key的list裡面搜尋，因為timestamp是照順序的，所以所有的pair預設就已經照著timestamp排序完成了

Code

這次寫的又和以前的不太一樣，search那邊的邏輯有變更，額外使用了cand(candidate)變數來儲存可能的結果

class TimeMap {
    private HashMap<String, List<Pair<String, Integer>>> map;

    public TimeMap() {
        map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        // Init.
        if (!map.containsKey(key)) map.put(key, new ArrayList<>());

        // Add the new value and timestamp
        map.get(key).add(new Pair(value, timestamp));
    }
    
    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) return "";

        // Find the pair base on timestamp
        List<Pair<String, Integer>> list = map.get(key);
        return search(list, timestamp);
    }

    private String search(List<Pair<String, Integer>> list, int timestamp) {
        int l = 0, r = list.size() - 1;

        String cand = "";

        // <=是為了把r指向的值也看過
        while (l <= r) {
            int mid = l + (r - l) / 2;

            int midTime = list.get(mid).getValue();

            if (midTime == timestamp) {
                return list.get(mid).getKey();
            } else if (midTime < timestamp) {
                // 也可能相同timestamp不存在，所以這邊要儲存最接近的值
                cand = list.get(l).getKey();
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return cand;
    }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */