2349. 設計數字容器系統

小貼士：unordered_map鍵值對的值可以是集合set或是優先隊列priority_queue。

思路

change函數會修改位於某位置容器的數值，用哈希表（unordered_map）去紀錄當前位置的數字。

最需要性能開銷的地方在find函數，因此重點在於提高它找到最小index的速度。
目標要找到最小index，而同樣的數字可以被放到很多容器，需要紀錄它所在的每一個位置，
不能單單紀錄最小值，因為那個位置可能被後來的數字佔去。

C++中，能有序排序內容的容器有兩個，set跟priority_queue，
所以用它們紀錄當前佔有的所有數字位置。

set可以在「位置被搶走」之後立刻更新，因此find函數能檢查非空之後，直接取第一個數字。
priority_queue則是把過去紀錄也留下來，在find取數字時再判斷number是否還佔有這個位置， 當確認此時也佔有時，找到答案。

程式碼

1. 哈希表 + 集合

class NumberContainers {
private:
    // nums[index] = num; 容器 index 中裝的數字
    unordered_map<int, int> nums;
    // indexs[numbers] = 數字 num 目前佔有的位置
    unordered_map<int, set<int>> indexs;
public:
    NumberContainers() {}

    void change(int index, int number) {
        // 原本位於 index 容器中的數字 nums[index] 被新進取代
        // 它失去了 index 這個位置。
        indexs[nums[index]].erase(index);
        nums[index] = number;
        indexs[number].insert(index);
    }

    int find(int number) {
        if(indexs[number].empty()) return -1;
        return *indexs[number].begin();
    }
};

2. 哈希表 + 優先隊列

class NumberContainers {
private:
    // nums[index] = num; 容器 index 中裝的數字
    unordered_map<int, int> nums;
    // indexs[numbers] = 數字 num 目前佔有的位置，從小到大排
    unordered_map<int, priority_queue<int, vector<int>, greater<int>>> indexs;
public:
    NumberContainers() {}
    void change(int index, int number) {
        // 使用 pq 不需要刪除，後面檢查時刪。
        nums[index] = number;
        indexs[number].push(index);
    }

    int find(int number) {
        auto& pq = indexs[number];
        while(!pq.empty() && nums[pq.top()] != number) {
            pq.pop();
        }
        return pq.empty() ? -1 : pq.top();
    }
};

複雜度分析

• $n$代表change被調用的次數
• 時間複雜度：find$函數$O(\log{n})$，`change`函數$O(\log{n})$或是$O(1)$（取決於有沒有需要保證最小值在最前）
• 空間複雜度：$O(n)$