LC.P432[全O(1)的数据结构]

方法一：双向链表+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
class AllOne {

    Node head, tail;
    Map<String, Node> map;

    public AllOne() {
        map = new HashMap<>();
        head = new Node(-1);
        tail = new Node(-1);
        head.next = tail;
        tail.prev = head;
    }

    public void inc(String key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.set.remove(key);
            int cnt = node.cnt;
            Node next = null;
            if (node.next.cnt == cnt + 1) {
                next = node.next;
            } else {
                next = new Node(cnt + 1);
                next.next = node.next;
                next.prev = node;
                node.next.prev = next;
                node.next = next;
            }
            next.set.add(key);
            map.put(key, next);
            clear(node);
        } else {
            Node node = null;
            if (head.next.cnt == 1) {
                node = head.next;
            } else {
                node = new Node(1);
                node.next = head.next;
                node.prev = head;
                head.next.prev = node;
                head.next = node;
            }
            node.set.add(key);
            map.put(key, node);
        }
    }

    public void dec(String key) {
        Node node = map.get(key);
        node.set.remove(key);
        int cnt = node.cnt;
        if (cnt == 1) {
            map.remove(key);
        } else {
            Node prev = null;
            if (node.prev.cnt == cnt - 1) {
                prev = node.prev;
            } else {
                prev = new Node(cnt - 1);
                prev.next = node;
                prev.prev = node.prev;
                node.prev.next = prev;
                node.prev = prev;
            }
            prev.set.add(key);
            map.put(key, prev);
        }
        clear(node);
    }

    public String getMaxKey() {
        Node node = tail.prev;
        for (String s : node.set) return s;
        return "";
    }

    public String getMinKey() {
        Node node = head.next;
        for (String s : node.set) return s;
        return "";
    }

    private void clear(Node node) {
        if (node.set.size() == 0) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }

    private static class Node {
        Set<String> set = new HashSet<>();
        int cnt;
        Node next, prev;

        public Node(int cnt) {
            this.cnt = cnt;
        }
    }
}

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * String param_3 = obj.getMaxKey();
 * String param_4 = obj.getMinKey();
 */
  • 时间复杂度：$O(1)$
  • 空间复杂度：$O(n)$