Первая проблема с уникальным номером - PullRequest
Новая
       49

Первая проблема с уникальным номером

1 голос
/ 28 апреля 2020

Итак, я недавно внедрил «Первый уникальный номер» в Leetcode. Вопрос, для справки, выглядит примерно так:

У вас есть очередь целых чисел, вам нужно получить первое уникальное целое число в очереди.

Реализация класса FirstUnique:

  • FirstUnique (int [] nums) Инициализирует объект с номерами в очереди.
  • int showFirstUnique () возвращает значение первого уникального целого числа очереди и возвращает -1, если такого целого числа нет.
  • void add (int value) вставить значение в очередь.

Моя реализация C ++ с использованием STL использует unordered_map и список. Карта хранит элементы очереди в виде ключей и сохраняет итератор, указывающий на элемент в списке, и логическое значение, указывающее на удаление значения из списка, когда оно перестает быть уникальным. Добавление и удаление элементов в списке являются операциями с постоянным временем. Тем не менее, мое решение намного медленнее по сравнению с другим решением, которое использует очередь и выполняет итерацию по очереди (в основном это O (n) по сравнению с моим O (1)).

Здесь явно хуже решение: 

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;
            }
        } 
    }
 };

Что я не понимаю, так это то, что, несмотря на мое быстрое решение, время выполнения намного медленнее. Тот, чья очередь составлял 328 мс, а мой - 532 мс по Leetcode. Я могу понять, что мое решение требует большой памяти, но не могу понять, почему оно медленнее.

Ответы [ 2 ]

1 голос
/ 29 апреля 2020

Нам нужно только pu sh уникальных значений в списке. Для отслеживания уникальных значений создайте неупорядоченную карту, которая отслеживает уникальные значения. 

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; 
        }

    }
};
0 голосов
/ 30 апреля 2020

Нам нужен только LinkedHashMap в Java. Который будет отслеживать заказы полученных предметов. В конструкторе мы просто отметим число, которое является уникальным. То же самое нужно сделать в методе 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);
    }
}
}
...