Структуры данных

Question

Существует большой поток чисел, таких как 5 6 7 2 3 1 2 3 .. Какая структура данных подходит для этой задачи, учитывая ограничения, что элементы должны быть вставлены в порядке убывания, а дубликаты должны быть удалены ,

Я не ищу код, просто идеи? Я думал о Self-Balancing BST, где мы могли бы добавить условие, что все узлы <текущий узел слева и все узлы> текущий узел справа, это заботится о дубликатах ... но я не думаю, что они обязательно вставляются в порядке убывания. Любые идеи, которые могли бы быть лучшим выбором ... конечно, это должно быть эффективным в отношении времени и пространства.

Answer 1

Хорошо сбалансированное двоичное дерево. Вы найдете или вставите каждый дубликат за O (log N), где N - количество элементов в дереве, поэтому O (N log N) в целом. И вставки заказаны - вы можете определить порядок, просто изменив сравнение.

Затем вы просто читаете его, как только он закончен в глубине первого порядка и, вуаля, по убыванию значений без дубликатов.

Ваш поток 5 6 7 2 3 1 2 3 приведет к:

    A>  5           B>  5           C>  6
                       /               / \
                      6               7   5

    D>  6           E>  6           F>  5
       / \             / \             / \
      7   5           7   3           6   2
           \             / \         /   / \
            2           5   2       7   3   1

тогда последние 2 и 3 отбрасываются, так как они уже существуют в дереве. И когда вы обрабатываете это дерево рекурсивно (влево, ток, вправо), вы получаете 7, 6, 5, 3, 2, 1 по желанию.

---

Другим решением, если у вас ограниченный диапазон чисел, является логическая карта. Допустим, диапазон ввода - только цифры от 0 до 9.

Установите логический массив из 10 элементов и установите для всех значений значение false. Им, для каждого числа, установите соответствующее значение в true.

Итак, для вашего ввода (пусто ложно, t верно):

      <booleans>
      0123456789
i  5|      t
n  6|      tt
p  7|      ttt
u  2|   t  ttt
t  3|   tt ttt
|  1|  ttt ttt
|  2|  ttt ttt
V  3|  ttt ttt

обратная обработка логической карты выдаст 7, 6, 5, 3, 2, 1.

Как только все числа получены, просмотрите массив в обратном порядке и выведите числа, значения которых равны true. Это O(n) операция времени, которая может занимать больше места (это общее правило, что вы часто можете обменять пространство на время при разработке алгоритмов).

Это также будет работать для диапазонов, не начинающихся с 0 - вам просто нужно сместить все на нижнюю границу диапазона. Таким образом, если бы диапазон был от 100 до 109, у вас все равно был бы массив из 10 элементов с индексом i, представляющим число i + 100.

Однако, если диапазон большой и числа редкие, я бы придерживался древовидной структуры.

Answer 2

Это зависит в некоторой степени от отношения дубликатов к общему размеру выборки.

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

Низкий коэффициент дублирования, просто используйте сбалансированное дерево, как вы предлагали.

Answer 3

Поскольку у вас есть простые данные, которые являются просто числами, почему бы вам не использовать двоичную кучу , хранящуюся в массиве? Конечно, вы должны знать верхнюю границу количества элементов, чтобы не перераспределять их ..