Java отсортированная структура данных, которая позволяет логарифмически c время удаления значений в пределах диапазона

Question

Мне было интересно, есть ли во встроенных библиотеках Java интерфейс, который реализует упорядоченную структуру данных и поддерживает удаление в определенном диапазоне. Например, если мы назовем структуру данных S (скажем, целых чисел), я хотел бы иметь возможность искать и удалять подмножество Q из S, так что Q состоит из всех элементов в S в диапазоне [начало, конец ] за время O (| Q | log | S |).

Я знаю, что в C ++ есть метод стирания в интерфейсе Set, но не похоже, что в TreeSet Java есть что-то аналогичный. Кто-нибудь может помочь? Спасибо!

Answer 1

SortedSet.subSet возвращает представление, которое затем можно clear().

Например:

TreeSet<String> set = new TreeSet<>(Arrays.asList("A", "B", "C", "D", "E"));
System.out.println(set);  //  [A, B, C, D, E]
set.subSet("B", "D").clear(); // Inclusive of B, exclusive of D.
System.out.println(set);  //  [A, D, E]

(Документация SortedSet описывает, как изменить границы subSet, чтобы они были исключающими и включающими соответственно, по крайней мере, для String).

Answer 2

Я не знаю никаких интерфейсов / библиотек, но вы можете попробовать использовать гистограмму, например структуру ...

Например, допустим, мы знаем, что наша структура будет содержать только целые числа от min до max включительно. Затем мы можем просто создать массив в следующем поместье ...

int[] hist = new int[max - min + 1];

Если мы хотим добавить число i к гистограмме, мы можем просто сделать ...

hist[i - min]++;

Каждый индекс в массиве представляет собой число в предопределенном диапазоне. Каждое значение в массиве представляет собой количество вхождений числа в диапазоне.

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

Допустим, мы хотите удалить все элементы в включающем диапазоне Q = [s, e]. Мы можем запустить следующую линейную l oop ...

for (int i = s; i <= e; i++) {
    hist[i - min] = 0;
}

Это выполняется в O(|Q|).

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

Для получения дополнительной информации проверьте https://en.wikipedia.org/wiki/Counting_sort.