Это одна из задач средней сложности в разделе Словари и хэш-карты набора задач для подготовки к собеседованию 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;
}