Problem 3 Implementation All O(1) data structure

Summary

• 这道不是让我们keep 时间顺序，这题是大小顺序

• 变化量为1（因为你每次最多增加1）的顺序模型

  • 对单一Data的每一次操作，导致的变化量至多为1:2D的结构设计

  • 单向排列次序不一定是个consecutive的次序

  • 当走流程的时候，新来一个key，走掉一个key，对于node的操作有很复杂，很可能新增或者删除现有的ListNode

    Node - Node - Node Freq2- Freq3 - Freq5

横向链接

• DLL + Map

• 对于所有变化量为1的reference Node我们可以实现对数量排序 + 所有对reference operation O(1)

纵向链接

• 对于同样横向属性的key，我们可以再做一个DLL+Map，也可以存一个collection(List, Map)

easy case

• 不需要任何的顺序， set/list

// Some code
class Node{
    Node prev;
    Node next;
    // Collection of keys share the same row field
    Set<String> allStringShareSameFreq;
}

hard case

• 同样的频率的情况下，对另一个field再进行比较和存储，再观察是不是变量为1的顺序模型again，如果是的话，可以再来一个map2+ dll2,而dll2 inside of dll1

// Some code
class Node{
    Node prev;
    Node next;
    // Store another DLL2
    AnotherOrderNode head;
    AnotherOrderNode tail
    // TreeMap, TreeSet
}

case even more

• 无限套娃

Middle Level：所有API走流程

• inc(String key)

  • case 1: 这个key是第一次出现

    • case1.1 看看有没有对应的freq =1 的node

      • 创建一个并且加入map +dll(set)

    • case1.2 如果已经存在在freq为1的弄的

      • 把这个新的data加入到已经存在的node set里面

  • case 2: 这个key不是第一次出现

    • 首先得知道他是第几次出现（map里面拿freq node）

    • 我们应该把这个node放到现在的freq+1的freq node

    • 这个freq + 1一定是你现在的freqNode.next么？

    • case2.1 不存在freq +1 的node

      • 创建一个freq + 1的freqNode并且把这个node插入到当前freqNode之后

      • 对应的key加入到这个你插入的freqNode里

    • case2.2 存在freq + 1的node

      • 对应的key加入到这个你插入的freqNode里

    • 不管存在不存在，现在key都不是freqNode里的人了，你得从freqNode里把这个key删除

      • 你现在把这个key当前的freqNode里删除之后，有没有可能当前的freqNode里就没有任何key了？

      • 如果空了，我们就要连着这个FreqNode + Map删除

• dec(String key)

  • case 1: 这个key是第一次出现

    • 直接return

  • case 2: 这个key不是第一次出现

    • 首先得知道他是第几次出现（map里面拿freq node）

    • 我们应该把这个node放到现在的freq+1的freq node

    • 这个key只出现了一次？我们不存在freq为0的FreqNode

      • 删除这个key + check freq为1的FreqNode是否需要删除

    • 这个freq - 1一定是你现在的freqNode.prev么？

    • case2.1 不存在freq - 1 的node

      • 创建一个freq - 1的freqNode并且把这个node插入到当前freqNode之前

      • 对应的key加入到这个你插入的freqNode里

    • case2.2 存在freq - 1的node

      • 对应的key加入到这个你插入的freqNode里

    • 不管存在不存在，现在key都不是freqNode里的人了，你得从freqNode里把这个key删除

      • 你现在把这个key当前的freqNode里删除之后，有没有可能当前的freqNode里就没有任何key了？

      • 如果空了，我们就要连着这个FreqNode + Map删除

• getMaxKey()

  • 从tailNode里随便拿一个

• getMinKey()

  • 从headNode里随便拿一个

// Some code

public class AllOne {
    MAp<String, FreqNode> map;
    FreqNopde head;
    FreqNode tail;
    public AllOne() {
        this.map = new HashMap<>();
        this.head = this.tail = new FreqNode(-1);
        head.next = tail;
        tail.prev = head;
        //如果不允许用dummy Node implement: this.head = this.tail = null;
    }
    
    public void inc(String key) {
        FreqNode = temp = map.get(key);
        if (temp == null) {
            FreqNode firstNode = this.head.next;
            if (firstNode.freq == 1) {
                firstNode.values.add(key);
                map.put(key, firstNode);
            }else {
                FreqNode newNode = insertNode(head, 1);
                newNode.values.add(key);
                map.put(key, firstNode);
            }
        } else {
            FreqNode next = temp.next;
            if (next.freq! = temp.freq + 1) {
                next = insertNode(temp, temp.freq + 1);
            }
            next.values.add(key);
            temp.values.remove(key);
            map.put(key, next);
            if (temp.values.size() == ) {
                deleteNode(temp);
            }
        }
    }

    public void dec(String key) {
        FreqNode temp = map.get(key);
        if (temp == null) {
            return;
        } else {
            if (temp.freq == 1) {
                temp.values.remove(key);
                if (temp.values.size() == 0) {
                    deleteNode(temp);
                }
                map.remove(key);
                return;
            }
            FreqNode previous = temp.prev;
            if (previous.freq != temp.freq - 1) {
                previous = insertNode(previous, temp.freq - 1);
            }
            temp.values.remove(key);
            previous.values.add(key);
            map.put(key, previous);
            if (temp.values.size() == 0) {
                deleteNode(temp);
            }
        }
    }
    
    public String getMapKey() {
        if (head.next == tail) {
            return "";
        }
        FreqNode maxNode = tail.prev;
        return maxNode.values.iterator().next();
    }
    
    public String getMinKey() {
        if (head.next == tail) {
            return "";
        }
        FreqNode minNode = head.next;
        return minNode. values.iterator().next();
    }
    
    class FreqNode {
        int freq;
        Set<String> values; //二级结构里同享一个freq的所有string们
        FreqNode next;
        FreqNode prev;
        public FreqNode(int freq) {
            this.freq = freq;
            this.values = new HashSet<>();
            this.next = this.prev = null;
        }
    }
    private FreqNode insertNode(FreqNode current, int freq) {
        FreqNode newNode = new FreqNode(freq);
        FreqNode next = current.next;
        current.next = newNode;
        newNode.next = next;
        next.prev = newNode;
        newNode.prev = current;
        return newNode;
    }
    
    private void deleteNode(FreqNode current) {
        FreqNode next = current.next;
        FreqNode prev = current.prev;
        prev.next = next;
        next.prev = prev;
        current.next = null;
        current.prev = null;
    }
}