432. All O(1) Data Structure #

题目 #

设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。

实现 AllOne 类：

AllOne() 初始化数据结构的对象。
inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。
dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。
getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 "" 。
getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 "" 。

**注意：**每个函数都应当满足 O(1) 平均时间复杂度。

思路 #

采用 双向链表 + 哈希表 的方式实现。
链表结点记录频率以及 该频率对应的字符串集合，以 Max <–> Min 的顺序存储。
HashSet 可以在 O(1) 的时间复杂度内实现 add 和 remove 操作。

代码 #

class AllOne {
    private class ListNode {
        public int count;
        public Set<String> collection;
        public ListNode prev;
        public ListNode next;
        
        ListNode(int count, ListNode prev, ListNode next) {
            this.count = count;
            this.collection = new HashSet<>();
            this.prev = prev;
            this.next = next;
        }
    }
    
    private ListNode sentinel;
    private Map<String, ListNode> map;
    
    public AllOne() {
        this.sentinel = new ListNode(-1, null, null);
        this.sentinel.prev = this.sentinel.next = this.sentinel;
        
        this.map = new HashMap<>();
    }
    
    /** Max <--> Min */
    public void inc(String key) {
        if (this.map.containsKey(key) == false) {
            if (this.sentinel.prev.count != 1) {
                this.sentinel.prev = new ListNode(1, this.sentinel.prev, this.sentinel);
                this.sentinel.prev.prev.next = this.sentinel.prev;
            }
            this.sentinel.prev.collection.add(key);
            this.map.put(key, this.sentinel.prev);
            return;
        }
        
        ListNode ptr = this.map.get(key);
        
        ptr.collection.remove(key);
        
        /** 将 key 提升到频率为 (ptr.count + 1) 的结点集合里 */
        if (ptr.prev.count != ptr.count + 1) {
            ptr.prev = new ListNode(ptr.count + 1, ptr.prev, ptr);
            ptr.prev.prev.next = ptr.prev;
        }
        ptr.prev.collection.add(key);
        this.map.put(key, ptr.prev);
        
        /** 若 collection 为空，表明当前不存在频率为 ptr.count 的字符串，移除 ptr 结点 */
        clean(ptr);
    }
    
    /** Max <--> Min */
    public void dec(String key) {
        ListNode ptr = this.map.get(key);
        
        ptr.collection.remove(key);
        
        if (ptr.count -1 == 0) {
            this.map.remove(key);
            clean(ptr);
            return;
        }
        
        /** 将 key 下放到频率为 ptr.count-1 的结点集合里 */
        if (ptr.next.count != ptr.count -1) {
            ptr.next = new ListNode(ptr.count-1, ptr, ptr.next);
            ptr.next.next.prev = ptr.next;
        }
        ptr.next.collection.add(key);
        this.map.put(key, ptr.next);
        
        /** 若 collection 为空，表明当前不存在频率为 ptr.count 的字符串，移除 ptr 结点 */
        clean(ptr);
    }
    
    public void clean(ListNode ptr) {
        if (ptr.collection.size() == 0) {
            ptr.prev.next = ptr.next;
            ptr.next.prev = ptr.prev;
        }
    }
    
    public String getMaxKey() {
        ListNode ptr = this.sentinel.next;
        for(String str: ptr.collection) return str;
        return "";
    }
    
    public String getMinKey() {
        ListNode ptr = this.sentinel.prev;
        for(String str: ptr.collection) return str;
        return "";
    }
}

致谢 #

宫水三叶