Какая структура данных эффективно поддерживает данные операции - PullRequest
2 голосов
/ 12 апреля 2020

Мне нужно подумать о структуре данных, которая эффективно поддерживает следующие операции:
1) Добавить целое число x
2) Удалить целое число с максимальной частотой (если имеется более одного элемента с одинаковыми Максимальная частота удалить все из них).
Я думаю о реализации дерева сегментов, где каждый узел хранит индекс своего дочернего элемента, имеющего наибольшую частоту.
Любые идеи или предложения о том, как подойти к этой проблеме или как это должно быть будет любезно оценен.

Ответы [ 3 ]

3 голосов
/ 13 апреля 2020

Мы можем использовать комбинацию структур данных. Hash_map для поддержания частотных отображений, где ключом является целое число, и значение указателя на узел «частоты», представляющий значение частоты, и набор целых чисел, имеющих одинаковую частоту. Частотные узлы будут поддерживаться в списке, упорядоченном по значениям частот.

Узел частоты может быть определен как

class Freq {
   int frequency;
   Set<Integer> values_with_frequency;
   Freq prev;
   Freq next;
}

Элементы HashMap будут тогда содержать записи вида

Entry<Integer, Freq>

Итак, для моментального снимка набора данных, такого как a,b,c,b,d,d,a,e,a,f,b, где буквы обозначают целые числа, будет выглядеть следующая структура данных:

c -----> (1, [c, e, f])
    |
    |
e --
    |
    |
f --

a -----> (3, [a, b])
    |
    |
b --

d --> (2, [d])

Узлы Freq будут поддерживаться в связанном списке, скажем freq_nodes, , отсортированными по значению частоты. Обратите внимание, что, как объяснено ниже, для сохранения списка, отсортированного по операциям добавления / удаления, не потребуется никакой операции log (n).

Способ выполнения операций add(x) и delete_max_freq() быть реализовано следующим образом:

add (x): Если x не найден в карте elements, проверьте, содержит ли первый элемент freq_nodes объект Freq с частотой 1 Если так, добавьте x к набору values_with_frequency объекта Freq. В противном случае создайте новый объект Freq с 1 в качестве значения частоты и x, добавленным к (теперь только один элемент) упакованному набору values_with_frequency

В противном случае (т. Е. Если x уже присутствует на карте elements ), следуйте указателю в значении записи, соответствующей элементам x в объекте Freq в freq_nodes, удалите x из поля values_with_frequency объекта Freq, отметив текущее значение частоты x, которое является значением elements.get(x).frequency (удерживайте это значение, скажем, F). Если набор values_with_frequency отображается пустым из-за этого удаления, удалите соответствующий узел из связанного списка freq_nodes. Наконец, если следующий узел Freq в связанном списке freq_nodes имеет частоту F + 1, просто добавьте x в поле values_with_frequency следующего узла. В противном случае просто создайте узел Freq, как это было сделано в случае несуществования узла Freq с частотой 1 выше.

Наконец, добавьте запись (x, Freq) на карту elements. Обратите внимание, что вся эта операция добавления (x) будет иметь значение O (1) во времени.

Вот пример последовательности операций add () с состоянием подпоследовательности данных структура.

добавить (а)

a -> N1 :       freq_nodes :   |N1 (1,  {a}) |   ( N1 is actually a Freq object)

добавить (б)

a -> N1 :        freq_nodes :   |N1 (1,  {a, b}) | 
b -> N1

добавить (a) В этот момент 'a' указывает на N1, однако его текущая частота равна 2, поэтому нам нужно вставить узел N2 рядом с N1 в DLL, после удаления его из values_with_frequency set из N1 * {{ , b}

a -> N2 :       freq_nodes :   |N1 (1,  {b}) |  --> |N2 (2,  {a}) | 
b -> N1

Интересно отметить, что каждый раз, когда мы увеличиваем частоту существующего элемента с F до F + 1, нам нужно сделать следующее

if (next node has a higher frequency than F+1 or we have reached the end of the list):

     create a new Freq node with frequency equal to F+1 (as is done above) 
     and insert it next to the current node
else :
    add ‘a’ (the input to the add() operation) to the ```values_with_frequency``` set of the next node

Операция delete_max_freq () будет просто включать удаление последней записи связанного списка freq_nodes и итерацию по ключам в набранном наборе values_with_frequency для удаления соответствующих ключей из elements карта. Эта операция заняла бы O (k) время, где k - количество элементов с максимальной частотой.

2 голосов
/ 12 апреля 2020

Мои мысли:

  • Вам понадобятся 2 карты.

  • Карта 1: целое число как ключ с частотой в качестве значения.

  • Карта 2: иметь карту частот в виде ключей и список целых чисел в качестве значений.

  • Добавить целое число: Добавить целое число на карту 1. Получить частоту. Добавьте его в список частотных ключей на карте 2.

  • Удалить целое число: очевидно, что мы можем поддерживать максимальную частоту в переменной для этих операций. Теперь удалите ключ из map2, который имеет эту максимальную частоту и максимальную частоту уменьшения.

  • Таким образом, производительность добавления и удаления должна быть в среднем O (1).


В приведенном выше сценарии у нас все еще будут целые числа на карте 1, которые существуют и имеют частоту, которая нереалистична c после удаления из карты 2. В этом случае, когда добавляется то же целое число , мы делаем обновление по требованию на карте 1, означающее, что если текущая частота на карте 1 не существует на карте 2 для этого целого числа, это означает, что она была удалена, и мы можем сбросить ее до 1.


Реализация:

import java.util.*;
class Foo{
    Map<Integer,Integer> map1;
    Map<Integer,Set<Integer>> map2;
    int max_freq;
    Foo(){
        map1 = new HashMap<>();
        map2 = new HashMap<>();
        map2.put(0,new HashSet<>());
        max_freq = 0;
    }


    public void add(int x){
        map1.putIfAbsent(x,0);
        int curr_f = map1.get(x);
        if(!map2.containsKey(curr_f)){
            map1.put(x,1);
        }else{
            map1.merge(x,1,Integer::sum);
        }

        map2.putIfAbsent(map1.get(x),new HashSet<>());
        map2.get(map1.get(x)-1).remove(x); // remove from previous frequency list
        map2.get(map1.get(x)).add(x);// add to current frequency list
        max_freq = Math.max(max_freq,map1.get(x));
        printState();
    }

    public List<Integer> delete(){
        List<Integer> ls = new ArrayList<>(map2.get(max_freq));
        map2.remove(max_freq);
        max_freq--;
        while(max_freq > 0 && map2.get(max_freq).size() == 0) max_freq--;
        printState();
        return ls;
    }

    public void printState(){
        System.out.println(map1.toString());
        System.out.println("Maximum frequency: " + max_freq);
        for(Map.Entry<Integer,Set<Integer>> m : map2.entrySet()){
            System.out.println(m.getKey() + " " + m.getValue().toString());
        }
        System.out.println("----------------------------------------------------");
    }

}

Демонстрация: https://ideone.com/tETHKV

Примечание: Звонок на delete() амортизируется.

2 голосов
/ 12 апреля 2020

Предполагая, что «эффективный» относится к тому, как сложность этих операций масштабируется в стиле big-O, я бы рассмотрел что-то, состоящее из:

  • хеш-карты с целыми числами в качестве ключей и их частот в качестве значений
  • древовидная структура (возможно, дерево двоичного поиска, например), где его узлы имеют число, представляющее частоту, и хэш-набор чисел, имеющих эту частоту.

Когда номер вставлен: 1. Найдите номер в хэш-карте, чтобы найти его частоту. (O(1)) 2. Найдите частоту в дереве (O(log N)). Удалить номер из его коллекции (O(1)). Если коллекция пуста, удалите частоту из дерева (O(log N)). 3. Увеличьте частоту числа. Установите это значение в хэш-карте (O(1)). 4. Найдите его новую частоту в дереве (O(log N)). Если он есть, добавьте номер в коллекцию (O(1)). Если нет, добавьте новый узел с номером в его коллекции (O(log N)).

При удалении элементов с максимальной частотой: 1. Удалите узел с самым высоким значением из дерева (O(log N)). 2. Для каждого номера в коллекции этого узла удалите запись этого номера из хэш-карты (O(1) для каждого удаленного номера).

Если у вас есть N номеров для добавления и удаления, ваш наихудший сценарий должен быть O(N log N) независимо от фактического распределения частот или порядка, в котором числа добавляются и удаляются.

Если вам известны какие-либо предположения, которые можно сделать относительно добавляемых чисел, возможно, вы могли бы сделать дополнительные улучшения, такие как используя индексированный массив, а не упорядоченное дерево. Но если ваши входные данные довольно неограниченные, это выглядит как довольно хорошая структура для обработки всех операций, которые вы хотите, не попадая в O(n²) территорию.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...