Возможно, я не использую правильную структуру данных. Мне нужно использовать набор, но также хочу эффективно возвращать k-й наименьший элемент. Может ли TreeSet в java сделать это? Для этого не существует встроенного метода TreeSet.
Пожалуйста, помогите мне.
Я не считаю, что TreeSet имеет метод, который делает это прямо. Существуют двоичные деревья поиска, которые поддерживают произвольный доступ O (log n) (их иногда называют деревьями статистики заказов), и есть Java-реализации этой структуры данных. Эти структуры обычно реализуются как двоичные деревья поиска, которые хранят информацию в каждом node, подсчитывая, сколько элементов находится слева или справа от node, поэтому поиск по дереву можно сделать, чтобы найти соответствующий элемент, спустившись в соответствующее поддерево на каждом шаге. В классической книге "Введение в алгоритмы, третье издание" Кормена, Ривеста, Лейсссона и Штайн исследует эту структуру данных в своей главе "Дополнительные структуры данных", если вам интересно, как реализовать ее самостоятельно.
В качестве альтернативы вы можете (в некоторых случаях) использовать метод TreeSet tailSet и модифицированный двоичный поиск, чтобы попробовать найти k-й элемент. В частности, посмотрите на первый и последний элементы TreeSet, затем (если возможно, с учетом содержимого) выберите какой-либо элемент, который находится на полпути между ними, и передайте его как аргумент tailSet, чтобы получить представление о элементах набор после середины. Используя количество элементов в tailSet, вы можете решить, находили ли вы этот элемент, или исследовать левую или правую половину дерева. Это немного измененный поиск интерполяции по дереву и потенциально может быть быстрым. Тем не менее, я не знаю внутренней сложности методов tailSet, поэтому на самом деле это может быть хуже, чем дерево статистики заказа. Он также может выйти из строя, если вы не можете вычислить "среднюю точку" двух элементов, например, если вы сохраняете String в своем TreeSet.
Надеюсь, это поможет!
Вам просто нужно перебрать элемент k. Один из способов сделать это - использовать один из Guava Iterables. получить методы:
T element = Iterables.get(set, k);
Нет встроенного метода для этого, потому что Set не является List, а операции с индексами, как правило, зарезервированы для List s. A TreeSet более подходит для таких вещей, как поиск ближайшего содержащегося элемента, который является >= некоторое значение.
Одна вещь, которую вы могли бы сделать, если бы самый быстрый доступ к k-му наименьшему элементу действительно была важна, заключалась бы в использовании ArrayList, а не TreeSet и вставки дескриптора путем двоичного поиска точки вставки и либо вставки элемента при этом индексе или замене существующего элемента на этот индекс, в зависимости от результата поиска. Затем вы можете получить k-й наименьший элемент в O (1), просто позвонив get(k).
Вы даже можете создать реализацию SortedSet, которая обрабатывает все это и добавляет метод get(index), если вы действительно этого хотели.
Используйте TreeSet.iterator(), чтобы получить итератор в порядке возрастания и вызвать next() K раз:
// Example for Integers
Iterator<Integer> it = treeSet.iterator();
int i = 0;
Integer current = null;
while(it.hasNext() && i < k) {
current = it.next();
i++;
}
У меня была та же проблема. Поэтому я взял исходный код java.util.TreeMap и написал IndexedTreeMap. Он реализует мою собственную IndexedNavigableMap:
public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
K exactKey(int index);
Entry<K, V> exactEntry(int index);
int keyIndex(K k);
}
Реализация основана на обновлении весов node в красно-черном дереве при его изменении. Вес - это число дочерних узлов ниже заданного node, плюс один. Например, когда дерево поворачивается влево:
private void rotateLeft(Entry<K, V> p) {
if (p != null) {
Entry<K, V> r = p.right;
int delta = getWeight(r.left) - getWeight(p.right);
p.right = r.left;
p.updateWeight(delta);
if (r.left != null) {
r.left.parent = p;
}
r.parent = p.parent;
if (p.parent == null) {
root = r;
} else if (p.parent.left == p) {
delta = getWeight(r) - getWeight(p.parent.left);
p.parent.left = r;
p.parent.updateWeight(delta);
} else {
delta = getWeight(r) - getWeight(p.parent.right);
p.parent.right = r;
p.parent.updateWeight(delta);
}
delta = getWeight(p) - getWeight(r.left);
r.left = p;
r.updateWeight(delta);
p.parent = r;
}
}
updateWeight просто обновляет весы до корня:
void updateWeight(int delta) {
weight += delta;
Entry<K, V> p = parent;
while (p != null) {
p.weight += delta;
p = p.parent;
}
}
И когда нам нужно найти элемент по индексу, это реализация, использующая вес:
public K exactKey(int index) {
if (index < 0 || index > size() - 1) {
throw new ArrayIndexOutOfBoundsException();
}
return getExactKey(root, index);
}
private K getExactKey(Entry<K, V> e, int index) {
if (e.left == null && index == 0) {
return e.key;
}
if (e.left == null && e.right == null) {
return e.key;
}
if (e.left != null && e.left.weight > index) {
return getExactKey(e.left, index);
}
if (e.left != null && e.left.weight == index) {
return e.key;
}
return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}
Также очень удобно найти индекс ключа:
public int keyIndex(K key) {
if (key == null) {
throw new NullPointerException();
}
Entry<K, V> e = getEntry(key);
if (e == null) {
throw new NullPointerException();
}
if (e == root) {
return getWeight(e) - getWeight(e.right) - 1;//index to return
}
int index = 0;
int cmp;
if (e.left != null) {
index += getWeight(e.left);
}
Entry<K, V> p = e.parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
while (p != null) {
cmp = cpr.compare(key, p.key);
if (cmp > 0) {
index += getWeight(p.left) + 1;
}
p = p.parent;
}
} else {
Comparable<? super K> k = (Comparable<? super K>) key;
while (p != null) {
if (k.compareTo(p.key) > 0) {
index += getWeight(p.left) + 1;
}
p = p.parent;
}
}
return index;
}
Результат этой работы можно найти в http://code.google.com/p/indexed-tree-map/. Переместился на https://github.com/geniot/indexed-tree-map
[Ниже я сокращаю "операцию поиска по наименьшему элементу kth" как " Kth op." ]
Вам нужно предоставить более подробную информацию. Какие операции обеспечит ваша структура данных? K в операции Kth очень мала по сравнению с N, или это может быть что угодно? Как часто у вас есть вставки и удаления по сравнению с поиском? Как часто у вас будет Kth наименьший поиск элементов по сравнению с поиском? Вы ищете быстрое решение нескольких строк в библиотеке Java или готовы ли вы потратить некоторое время на создание пользовательской структуры данных?
Операциями для предоставления может быть любое подмножество:
LookUp (найдите элемент по его ключу, где ключ сопоставим и может быть любым)
Вставить
Удалить
Kth
Вот несколько возможностей:
Если не будет/очень мало добавлений и удалений, вы можете просто отсортировать элементы и использовать массив, используя O (Log (N)) время поиска и O (1) для Kth.
Если O (Log (N)) для LookUp, Вставить, Удалить и O (k) для Kth op. достаточно хорошо, возможно, самой простой реализацией будет "Пропустить списки". (Статья Википедии очень хороша, если вам нужно больше деталей)
Если K достаточно мало или операции Kth будут выполняться только после "фазы вставки и фазы удаления", вы можете сохранить наименьшее K strong > элементов в куче, сортировка после вложений & удаление для O (N + k Log k). (Вам также понадобится отдельный хэш для LookUp)
Если K является произвольным, а O (N) достаточно хорош для операции Kth, вы можете использовать Hash для O (1), и используйте алгоритм "односторонний-QuickSort" для операций Kth (основная идея - это быстрый поиск, но только для каждой репликации двоичных разделов на стороне, которая вам действительно нужна, что дало бы (это грубое упрощение) N (1/2 + 1/4 + 1/8 +...) = O (N) ожидаемое время)
Вы можете создать дополненную "простую" структуру дерева интервалов с каждым node, сохраняя число своих детей, чтобы LookUp, Вставить, Удалить, Kth все вычисления в O (Log N), если дерево сбалансировано, но, возможно, это будет непросто реализовать, если вы являются новичком.
и т.д.. и т.д. Набор альтернатив бесконечен, как возможные интерпретации вашего вопроса.
TreeSet<Integer> a=new TreeSet<>();
a.add(1);
a.add(2);
a.add(-1);
System.out.println(a.toArray()[0]);
это может быть полезно
Не могли бы вы использовать ConcurrentSkipListSet и использовать метод toArray()? ConcurrentSkipListSet сортируется по естественному порядку элементов. Единственное, о чем я не уверен, это то, что toArray() - это O (n), или поскольку он поддерживается списком (с поддержкой массива, например ArrayList), он O (1).
Если toArray() - O (1), вы должны быть skipList.toArray() [k], чтобы получить k-й наименьший элемент.
Я знаю, что этот вопрос довольно старый, но поскольку TreeSet реализует NavigableSet, у вас есть доступ к методу subSet, который выполняется в постоянное время.
subSet(k, k + 1).first();
Первый() вызов принимает log (n) время, где n - размер исходного набора. Это создает некоторые ненужные объекты, которых можно избежать с помощью более надежной реализации TreeSet, но он избегает использования сторонней библиотеки.