432. 全O(1)的數據結構

思路

1. inc(string key)，要提升key的計數。

2. dec(string key)，要降低key的計數。

3. getMaxKey()，要回傳計數最多的key。

4. getMinKey()，要回傳計數最少的key。
   這個題目不可能用map，因為維持有序的關係，排序本身就 $O(n\log{n})$ 了。

對於此題，既要維持有序，來得知出現最多跟最少的單字，

又要能根據函數呼叫，快速修改單字的出現頻率。還要求 $O(1)$ 的時間複雜度。

假如單純用unordered_map紀錄頻率，當要找出現頻率最多與最少的資料時，

就需要花 $O(n)$ 的時間找遍整個unordered_map。

若是用排序，因為要最大和最小，可以用heap去找，但是修改元素後需要花 $O(\log{n})$ 去調整。

每次頻率的變化都只會是$±1$。都是相鄰的，可以用雙向鏈表去做。

• 用排序的邏輯是：有人分數$±1$，整個班級重新比一次賽。
• 鏈結串列的邏輯：有人分數$±1$，走到相鄰的房間（節點）中，房間的編號（cnt）就是當前的分數。

1. 為了避免nullptr引來的一系列問題，初始化時開兩個節點，一個編號0，一個編號INT_MAX。

• 額外初始化一個unordered_map<string, DoubleNode>，用來快速找到現在字串在哪一個節點。

2. inc(string key)：當新的字串加入時

• 如果字串是新的，就移動到一號節點，假如一號節點並不存在，創建一號節點，並加入到節點的uset中。
• 如果字串是舊的，移動到下一個節點，下一個節點的cnt應該要是當前房間+1，如果不是，在當前節點跟下一個節點之間插入一個新的節點，cnt是當前節點+1
• 假如移動之後，原先的節點沒有字串，刪除該節點

呼叫函數時，相當於key這個人的編號加一。

• 假如他不在任何房間，代表他是新學生，要去房間1。
• 假如他在房間，舊學生，去他現在房間的下一個房間，如果房間還沒開，就開一個，並跟其他房間相連。
• 前往下個房間後，原先房間沒有人，關掉舊房間。

3. dec(string key)：當刪除字串時（必定是已經出現過的）

• 如果字串的出現頻率是 1，將umap中的資訊刪掉。
• 其餘判斷相同。

4. 找最大以及最小。

• head 指針後的第一個節點，紀錄著計數最少的字串。
• tail 指針前的第一個節點，紀錄著計數最多的字串。

程式碼

雙向鏈表 + 哈希表

struct DoubleNode {
    int cnt; // 出現頻率
    unordered_set<string> uset; // 出現頻率為 cnt 的單字
    DoubleNode *prev, *next;
    DoubleNode(string s, int c) : cnt(c), prev(nullptr), next(nullptr) {
        uset.insert(s);
    }
};
class AllOne {
private:
    unordered_map<string, DoubleNode*> umap;
    DoubleNode *head;
    DoubleNode *tail;
    void insert(DoubleNode* cur, DoubleNode* newNode) { // 在 curNode 的後面插入 newNode
        cur->next->prev = newNode;
        newNode->next = cur->next;
        cur->next = newNode;
        newNode->prev = cur;
    }
    void remove(DoubleNode* cur) {
        cur->prev->next = cur->next;
        cur->next->prev = cur->prev;
        delete cur;
    }
public:
    AllOne() {
        head = new DoubleNode("", 0);
        tail = new DoubleNode("", INT_MAX);
        tail->prev = head;
        head->next = tail;
    }
    
    void inc(string key) {    
        if(!umap.contains(key)) {
            if(head->next->cnt == 1) { // 有創建過節點
                head->next->uset.insert(key); // 對應的節點加入新的數字
                umap[key] = head->next;
            }
            else {
                DoubleNode* newNode = new DoubleNode(key, 1);
                insert(head, newNode);
                umap[key] = newNode;
            }
        }
        else { // 曾經有過這個 key 
            DoubleNode* node = umap[key];
            if(node->next->cnt == node->cnt + 1) {
                node->next->uset.insert(key);
                umap[key] = node->next;
            }
            else { // 下一個節點的數量不對
                // 創建新的節點, 將自己加入
                DoubleNode* newNode = new DoubleNode(key, node->cnt + 1);
                insert(node, newNode);
                umap[key] = newNode;
            }
            node->uset.erase(key); // 自原先節點刪除
            if(node->uset.empty()) { // 檢查原先節點有沒有元素，如果沒有則刪除節點
                remove(node);
            }
        }
    }
    
    void dec(string key) {
        // 降低的必定是以前曾經加入過的
        DoubleNode* node = umap[key];
        if(node->cnt == 1) {
            umap.erase(key);
        }
        else {
            if(node->prev->cnt == node->cnt - 1) {// 曾經創建過上個節點
                node->prev->uset.insert(key);
                umap[key] = node->prev;
            }
            else {
                DoubleNode* newNode = new DoubleNode(key, node->cnt - 1);
                insert(node->prev, newNode);
                umap[key] = newNode;
            }
        }
        node->uset.erase(key); // 從當前節點紀錄刪除
        if(node->uset.empty()) {
            remove(node);
        }
    }
    
    string getMaxKey() {
        if(tail->prev == head) {
            return "";
        }
        return *(tail->prev->uset.begin());
    }
    
    string getMinKey() {
        if(head->next == tail) {
            return "";
        }
        return *(head->next->uset.begin());
    }
};

複雜度分析

• 時間複雜度：$O(1)$
• 空間複雜度：$O(n)$