#981. Time Based Key-Value Store

題目描述

設計一個基於時間序的鍵值資料結構，實現可以在不同時間點儲存具有相同鍵的資料以及獲取資料時可以指定某個時間戳上的資料。

實作Time Map類別：

TimeMap()
void set (String key, String value, int timestamp)儲存資料的鍵key、值value以及時間戳timestamp。
String get(String key, int timestamp)回傳之前呼叫過set的值，同時timestamp_prev <= timestamp。如果存在多個值，則回傳擁有最大timestamp_prev的值。如果沒有任何值存在，則回傳""。

限制條件

1 <= key.length, value.length <= 100
key和value由小寫英文字母和數字組成。
1 <= timestamp <= 10⁷
所有的呼叫set時輸入的時間戳timestamp都是嚴格遞增的。
單次測試最多只會呼叫2 * 10⁵次並且由set和get所組成。

解題思路

鍵值資料結構最好的方式就是使用Hashtable來處理。接著要按照時間順序儲存資料，使用List可以排序資料。

public class TimeMap {
    private Hashtable _keyStore;

    public TimeMap() {
        _keyStore = new Hashtable();
    }
    
    public void Set(string key, string value, int timestamp) {
        if(_keyStore.Contains(key)){            
            ((List<(int,string)>)_keyStore[key]).Add((timestamp,value));
        }
        else{
            _keyStore.Add(key,new List<(int,string)>(){(timestamp,value)});
        } 
    }
    
    public string Get(string key, int timestamp) {
        if(!_keyStore.Contains(key)) return "";
        var valueSet = (List<(int,string)>)_keyStore[key];        
        return Search(valueSet,timestamp);
    }

	private string Search(List<(int,string)> list, int target){
		for(int i=list.Count-1;i>=0;i--){
            (int ts,string val) = list[i];
            if(ts<=target) return val;
        }
		return "";
	}
}

複雜度分析：

時間複雜度：Set的時間複雜度為O(1)，Get的時間複雜度為O(n)，n為儲存的資料長度。
空間複雜度：空間複雜度為O(n)，n為儲存的所有資料長度。

Improvement

Get所呼叫的Search可以改成二元搜尋法，這樣時間複雜度就會是O(log n)。

private string Search(List<(int,string)> list, int target){       
	if(list.Count==0) return ""; 
	int left = 0;
	int right = list.Count;
	while(left<right){
		int mid = (left + right)/2;                   
		(int ts,string val) = list[mid];
		if(ts == target){
			return val;
		}else if(ts>target){                
			right = mid;
		}else if(ts<target){                
			left = mid+1;
		}
	}
	if(left>0 && left<=list.Count){
		(int ts,string val) = list[left-1];
		return val;
	}
	return "";
}

學習重點

Hashtable
Binary Search