Leetcode 981 基于时间的键值存储 红黑树与二分查找

　　JAVA 实现，基于红黑树：

class TimeMap {
        Map<String, TreeMap<Integer, String>> map = new HashMap<String, TreeMap<Integer, String>>();

        /**
         * Initialize your data structure here.
         */
        public TimeMap() {

        }

        public void set(String key, String value, int timestamp) {
            if (!map.containsKey(key)) map.put(key, new TreeMap<Integer, String>());
            map.get(key).put(timestamp, value);
        }

        public String get(String key, int timestamp) {
            if (!map.containsKey(key)) return "";
            TreeMap<Integer, String> tree = map.get(key);
            Integer searchKey = tree.floorKey(timestamp);
            return searchKey == null ? "" : tree.get(searchKey);
        }
    }

　　JS 实现，基于二分查找：

/**
 * Initialize your data structure here.
 */
var TimeMap = function () {
    this.map = new Map();
};

/**
 * @param {string} key
 * @param {string} value
 * @param {number} timestamp
 * @return {void}
 */
TimeMap.prototype.set = function (key, value, timestamp) {
    if (!this.map.has(key)) this.map.set(key, []);
    let timeElements = this.map.get(key);
    timeElements.push(new TimeElement(timestamp, value));
};

/**
 * @param {string} key
 * @param {number} timestamp
 * @return {string}
 */
TimeMap.prototype.get = function (key, timestamp) {
    if (!this.map.has(key)) return "";
    let timeElements = this.map.get(key), len = timeElements.length, leftPoint = 0, rightPoint = len - 1;
    while (leftPoint < rightPoint - 1) {
        let mid = Math.floor((leftPoint + rightPoint) / 2);
        if (timeElements[mid].timestamp < timestamp) leftPoint = mid;
        else rightPoint = mid;
    }
    let re = leftPoint + 1 < len && timeElements[leftPoint + 1].timestamp <= timestamp ? timeElements[leftPoint + 1] : timeElements[leftPoint];
    return re.timestamp <= timestamp ? re.value : "";
};

var TimeElement = function (timestap, value) {
    this.timestamp = timestap;
    this.value = value;
}

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