第一个唯一编号慢的运行时问题

Question

因此，我最近在Leetcode上实现了“第一个唯一编号”。供参考的问题是这样的：

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

实现FirstUnique类：

• FirstUnique（int [] nums）用中的数字初始化对象队列。
• int showFirstUnique（）返回队列的第一个唯一整数的值，如果没有这样的整数，则返回-1。
• void add（int value）将值插入队列。

我的使用STL的C ++实现使用unordered_map和一个列表。该映射将队列中的元素存储为键，并存储指向列表中元素的迭代器和一个布尔值，指示当值不再唯一时从列表中删除该值。向列表中添加和删除元素似乎是恒定时间操作。但是，与另一个使用队列并在队列中进行迭代的解决方案相比，我的解决方案要慢得多（与我的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; 
        }

    }
};

Answer 2

我们只需要Java中的LinkedHashMap。它将跟踪收到的物品的订单。在构造函数中，我们将仅标记唯一的数字。在add方法中可以完成相同的操作。在showFirstUnique中，我们将遍历地图并返回标记为唯一的地图。请参阅下面的代码以获取更多信息。

class FirstUnique {
Map<Integer, Integer> map;

public FirstUnique(int[] nums) {
    map = new LinkedHashMap<>();

    for (int num : nums) {
        if (map.containsKey(num)) {
            map.put(num, 0);
        } else {
            map.put(num, 1);
        }
    }
}

public int showFirstUnique() {
    for (Integer key : map.keySet()) {
        if (map.get(key) == 1) {
            return key;
        }
    }
    return -1;
}

public void add(int value) {
    if (map.containsKey(value)) {
        map.put(value, 0);
    } else {
        map.put(value, 1);
    }
}
}