🌕🌕 432. 全 O(1) 的数据结构

难度: 🌕🌕

问题描述

---

解法

class AllOne {
    // 思路：
    // 构造节点类，每个节点存放的是相同频次的 key 集合
    // 借助 HashMap<key, Node> 
    // 本来设计的是 HashMap<fre, key 集合> 记录 频次 - key 集合 的关系，但是这样求 maxCount & minCount 出现问题，无法得到
    // 举例：
    // 假设删掉某个 key 后 fre == 0 表示不存在，而 minCount 原本 == 1 且只有这一个 key，
    // 导致 minCount 得找 fre 次小 的 key 所在频次，而 HashMap 要找到次小的频次，只能遍历一遍 map，复杂度 O(N)
    // 而通过 自建节点类 就可以很方便找出 maxCount & minCount
    HashMap<String, Node> map;
    Node head;
    Node tail; // 虚拟头尾节点

    public AllOne() {
        map = new HashMap<>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }
    
    public void inc(String key) {
        int fre = 0;
        Node cur = head; // 假设之前不存在 key，那么前一个节点就是首节点
        if(map.containsKey(key)) {
            cur = map.get(key);
            fre = cur.fre;
        }
        Node next = cur.next;
        // 删除原 key 所在节点中 key 的存在
        if(cur != head) {
            deleteKey(cur, key);
        }
        // 将 key 放入下一频次所在的节点中
        fre ++;
        // 判断 新fre 是否存在节点，有则加入，无则创建
        if(next.fre == fre) {
            union(next, key);
            map.put(key, next);
        } else {
            Node node = new Node(fre, key);
            insertBefore(next, node);
            map.put(key, node);
        }

        // print("add " + key);
    }
    
    public void dec(String key) {
        Node cur = map.get(key);
        Node prev = cur.prev;
        int fre = cur.fre;
        fre --;
        deleteKey(cur, key);

        if(prev.fre == fre) {
            union(prev, key);
            map.put(key, prev);
        } else if(fre == 0) {
            map.remove(key);
        } else {
            Node node = new Node(fre, key);
            insertAfter(prev, node);
            map.put(key, node);
        }
        
        // print("del " + key);
    }
    
    public String getMaxKey() {
        if(head.next == tail) {
            return "";
        }
        return tail.prev.set.iterator().next();
    }
    
    public String getMinKey() {
        if(head.next == tail) {
            return "";
        }
        return head.next.set.iterator().next();
    }

    // 我是加入你们的
    private void union(Node node, String key) {
        HashSet<String> set = node.set;
        set.add(key);
    }

    private void insertAfter(Node prev, Node node) {
        Node next = prev.next;
        prev.next = node;
        node.prev = prev;
        node.next = next;
        next.prev = node;
    }
    private void insertBefore(Node next, Node node) {
        Node prev = next.prev;
        insertAfter(prev, node);
    }
    private void deleteNode(Node node) {
        Node prev = node.prev;
        Node next = node.next;
        prev.next = next;
        next.prev = prev;
    }
    private void deleteKey(Node node, String key) {
        node.set.remove(key);
        if(node.set.isEmpty()) {
            // System.out.println("deleteNode: " + node.fre + "  " + key);
            deleteNode(node);
        }
    }

    private void print(String order) {
        System.out.println(" ------  " + order);
        Node cur = head.next;
        while(cur.next != null) {
            if(!cur.set.isEmpty()) {
                System.out.println(cur.fre);
            }
            cur = cur.next;
        }
    }
}

class Node {
    int fre;
    HashSet<String> set;
    Node prev;
    Node next;
    public Node(int fre, HashSet<String> set) {
        this.fre = fre;
        this.set = set;
    }
    public Node(String key) {
        this.fre = 1;
        this.set = new HashSet<>();
        set.add(key);
    }
    public Node(int fre, String key) {
        this.fre = fre;
        this.set = new HashSet<>();
        set.add(key);
    }
    public Node(int fre) {
        this.fre = fre;
        this.set = new HashSet<>();
    }
    public Node() {
        this.fre = -1;
        this.set = new HashSet<>();
    }
}

/**
 * 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();
 */

---

输出