Leetcode -981- Time-based key-value storage

[Blog link]

The path to learning at 🐔

The nuggets home page

[Topic Description

Set (string key, string value, int timestamp) Stores key, value, and timestamp. 2. Get (string key, int timestamp) returns the value stored by the previous call to set(key, value, timestamp_prev), where timestamp_prev <= timestamp. If there are more than one such value, the value corresponding to the maximum timestamp_prev is returned. If there is no value, an empty string ("") is returned. Example 1: Enter: inputs = ["TimeMap","set","get","get","set","get","get"], Inputs = [[], [" f oo ", "bar", 1], [" foo ", 1], [" foo ", 3], [" foo ", "bar2", 4], [" foo ", 4], [" foo ", 5]] output: [null,null,"bar","bar",null,"bar2","bar2"] kv.set("foo", "bar", 1); // Store key "foo" and value "bar" and timestamp = 1 kv.get("foo", 1); // output "bar" kv.get("foo", 3); Kv.set ("foo", "bar2", 4); // Output "bar"; kv.get("foo", 4); // output "bar2" kv.get("foo", 5); // Output "bar2" Example 2: Input: inputs = ["TimeMap","set","set","get","get","get","get","get"], Inputs = [[], [" love ", "high", 10], [" love ", "low", 20], [" love ", 5], [" love ", 10], [" love ", 15], [" lov e ", 20], [" love ", 25]] output: [null, null, null, ""," high ", "high", "low", "low"] hint: all key/value string is lowercase. All key/value strings are in the range [1, 100]. Timestamps in all timemap. set operations are strictly incremented. 1 <= TIMESTAMP <= 10^7 The timemap. set and timemap. get functions are called (combined) a total of 120,000 times per test case. Related Topics Design binary lookup of hash table string 👍 82 👎 0Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: Double Map storage

• Two maps are used to store keyValue and valueTimeStamp respectively
• I feel that value can be optimized to store only one maximum value, but I am in a hurry to come back to see the solution of three leaves
• Here’s a hyperlink to the Trilobites
• A map nested array is a desirable optimization, but it’s fun to think of a red-black tree immediately following the delete operation! Very interesting topic

class TimeMap {


        private Map<String, Map<String, Integer>> keyMap;

        private Map<String, Integer> valueMap;


        public TimeMap(String key, String value, int timestamp) {
            this.valueMap.put(value, timestamp);
            this.keyMap.put(key, valueMap);
            System.out.println("null");
        }


        /** * Initialize your data structure here. */

        public TimeMap(a) {
            this.keyMap = new HashMap<>();

        }

        public void set(String key, String value, int timestamp) {
            Map<String, Integer> valueMap = this.keyMap.getOrDefault(key, new HashMap<>());
            valueMap.put(value, timestamp);
            this.keyMap.put(key, valueMap);
            System.out.println("null");
        }

        public String get(String key, int timestamp) {
            if (!this.keyMap.containsKey(key)) {
                System.out.println("null");
                return "";
            }
            String res = "";
            int max = 0;
            Map<String, Integer> valueMap = this.keyMap.get(key);
            for (Map.Entry<String, Integer> entry : valueMap.entrySet()
            ) {
                if (entry.getValue() < timestamp && entry.getValue() > max) {
                    max = entry.getValue();
                    res = entry.getKey();
                }
                if (entry.getValue() == timestamp) {
                    System.out.println(entry.getKey());
                    return entry.getKey();
                }
            }
            System.out.println("".equals(res) ? "null" : res);
            returnres; }}Copy the code

Set time complexity O(1) Get time complexity O(n), where n is the number of values corresponding to the key