c++ - 第一个唯一编号慢运行时问题

Question

所以我最近在 Leetcode 上实现了“First unique number”。供引用的问题是这样的:

您有一个整数队列，您需要检索队列中的第一个唯一整数。

实现 FirstUnique 类:

FirstUnique(int[] nums) 用数字初始化对象
队列。

int showFirstUnique() 返回队列的第一个唯一整数的值，如果没有这个整数则返回 -1。

void add(int value) 将值插入队列。

我使用 STL 的 C++ 实现使用 unordered_map 和列表。该映射将队列的元素存储为键，并存储指向列表中元素的迭代器和一个 bool 值，指示当该值不再唯一时从列表中删除该值。向列表中添加和删除元素似乎是恒定时间操作。但是，与使用队列并遍历队列的另一个解决方案相比，我的解决方案要慢得多(与我的 O(1) 相比，它基本上看起来是 O(n))。

这是显然更糟糕的解决方案:

class FirstUnique {
        private:
        queue<int> q;
        unordered_map<int, int> count;
        public:
        FirstUnique(vector<int>& nums) {
            for(int num: nums){
                count[num]++;
                q.push(num);
            }
        }

        int showFirstUnique() {
            while(!q.empty() && count[q.front()] > 1){
                q.pop();
            }
            if(q.empty()){
                return -1;
            }
            else{
                return q.front();
            }
        }

        void add(int value) {
            if(++count[value] == 1){
                q.push(value);
            }
        }
    };

这是我的解决方案:

class FirstUnique {
    public:
    unordered_map<int, pair<list<int>::iterator, bool>> hashmap;
    list<int> l;
    FirstUnique(vector<int>& nums) {
    for(auto it=nums.begin(); it!=nums.end(); it++)
        add(*it);
    }

    int showFirstUnique() {
        if (l.empty())
            return -1;
        return l.back();
    }

    void add(int value) {
        unordered_map<int, pair<list<int>::iterator, bool>>::iterator it = hashmap.find(value);
        if(it == hashmap.end())
        {
            l.push_front(value);
            hashmap[value] = make_pair(l.begin(), false) ;
        }

        else
        {
            if((it->second).second == false)
            {
                l.erase((it->second).first);
                (it->second).second = true;
            }
        } 
    }
 };

我不明白的是，尽管我的解决方案很快，但运行时要慢得多。在 Leetcode 上，有队列的运行时间为 328 毫秒，而我的运行时间为 532 毫秒。我可以理解我的解决方案内存很重，但不明白为什么它更慢。

Answer 1

我们只需要将唯一值推送到列表中。为了跟踪唯一值，创建一个跟踪唯一值的无序映射。

public:
    list<int> li;
    unordered_map<int, bool> m;
    FirstUnique(vector<int>& nums) {
        for(auto i:nums){

//         if i is not in map then we push i to the list an make m[i] = true i.e. unique
//         else we make it false. i.e. it is not unique now. 

            if(m.find(i) == m.end()){
                li.push_back(i);
                m[i] = true;
            }else{
                m[i] = false;
            }
        }

    }

    int showFirstUnique() {
        for(auto it:li){
            if(m[it] == true){
                return it;
            }
        }
        return -1;

    }

    void add(int value) {
        if(m.find(value) == m.end()){
            li.push_back(value);
            m[value] = true;
        }else{
            m[value] = false; 
        }

    }
};