Это одна из задач средней сложности в разделе Словари и хэш-карты набора задач для подготовки к собеседованию hackerrank. Ссылка здесь.
Проблема заключается в том, что вам предоставляется список запросов трех типов, которые должны выполняться в поддерживаемой вами структуре данных.
Query type 1
- это запрос на вставку, он вставляет значение в структуру данных.
Query type 2
удаляет ровно одно вхождение значения в вашей структуре данных, только если оно было ранее вставлено.
Query type 3
напечатает 1, если в структуре данных есть хотя бы значение, которое встречается k раз.
Вы должны реализовать эту функциональность, выполнить все запросы и вернуть результаты запросов типа 3.
Решение
Чтобы иметь возможность выполнять каждый из наших запросов в постоянное время, нам понадобится способ подсчета вхождений значений, вставленных или удаленных в запросах, и отслеживания количества появившихся значений с k
частотой в структуре данных за постоянное время.
Это можно сделать с помощью двух хэш-карт, одна для отслеживания частоты каждого вставленного значения, а другая для отслеживания количества значений с определенной частотой в структуре данных.
Таким образом, при вставке или удалении мы обновляем обе карты, а когда нам нужно создать количество элементов с частотой k, мы просто ищем k в хэш-карте, отслеживая эти данные. Мы только хотим быть особенно осторожными при реализации и не удалять элементы, если они не были вставлены ранее.
Код
РЕШЕНИЕ НА GITHUB (отформатированное) НАЖМИТЕ ЗДЕСЬ
vector<int> freqQuery(vector<vector<int>> queries) { int q; int type; int current_count; vector<int> query; vector<int> query_results; unordered_map<long, int> count_map; unordered_map<int, long> frequency_map; q = queries.size(); for(int i =0 ; i < q ;i++){ query = queries[ i ]; type = query[0]; switch(type){ case 1: frequency_map[count_map[ query[1] ]]--; count_map[ query[1] ]++; frequency_map[count_map[ query[1] ]]++; break; case 2: current_count = count_map[ query[1] ]; if(current_count > 0){ frequency_map[current_count]--; count_map[ query[1] ]--; frequency_map[count_map[ query[1] ]]++; } break; case 3: query_results.push_back(( frequency_map[query[1]] > 0 )? 1:0); break; default: break; } } return query_results; }