Comment faire pour retourner la kième élément TreeSet en Java
Peut-être que je ne suis pas à l'aide de la droite structure de données. J'ai besoin d'utiliser un jeu, mais veulent aussi efficacement retour de la k-ième plus petit élément. Peut TreeSet en java ce faire? Il ne semble pas intégré dans la méthode de TreeSet pour ce faire.
S'il vous plaît aider moi.
- Si la question d'origine est d'environ HashMap, cette question a une discussion de TreeMap ainsi. stackoverflow.com/questions/2656995/nth-item-of-hashmap
Vous devez vous connecter pour publier un commentaire.
Je ne crois pas que
TreeSet
a une méthode qui directement cette. Il y a des arbres binaires qui ne soutien de O(log n) à accès aléatoire (ils sont parfois appelés ordre statistique des arbres), et il y a Implémentations Java de cette structure de données disponibles. Ces structures sont généralement mis en œuvre comme des binaires de recherche arbres qui stockent des informations dans chaque nœud de calcul du nombre d'éléments sont à gauche ou à droite du nœud, donc une recherche en bas de l'arbre peut être fait pour trouver le bon élément en descendant dans l'arborescence à chaque étape. Le classique "Introduction aux Algorithmes, Troisième Édition" livre de Cormen, Rivest, Leisserson, et Stein explore cette structure de données dans leur chapitre "Développer des Structures de Données" si vous êtes curieux de savoir comment mettre en œuvre un vous-même.Sinon, vous pouvez peut-être (dans certains cas) pour utiliser le
TreeSet
'stailSet
méthode et une modification de recherche binaire pour essayer de trouver la kième élément. plus Précisément, le regard au premier et dernier éléments de laTreeSet
, puis (si possible au vu du contenu) choisir un élément qui est à mi-chemin entre les deux et de le passer en argument àtailSet
pour obtenir une vue des éléments de l'ensemble après le milieu. En utilisant le nombre d'éléments dans letailSet
, vous pouvez alors décider si vous avez trouvé l'élément, ou si vous souhaitez explorer la gauche ou la droite moitiés de l'arbre. C'est un peu modifié l'interpolation de recherche - dessus de l'arbre, et pourrait potentiellement être rapide. Cependant, je ne connais pas la complexité interne de latailSet
méthodes, ce qui pourrait être pire que de l'ordre de statistique de l'arbre. Il peut également échouer si vous ne pouvez pas calculer le "milieu" de deux éléments, par exemple, si vous stockezString
s dans votreTreeSet
.Espérons que cette aide!
tailSet
ouheadSet
d'unTreeSet
nécessite une itération à travers les éléments et de les compter. Alors votre suggestion au sujet de qui probablement ne va pas aider.Vous avez juste besoin d'accéder à l'élément k. Une façon de le faire serait d'utiliser l'un des Goyave's Iterables.obtenez de l' méthodes:
Il n'y a pas de méthode intégrée pour ce faire, car un
Set
n'est pas unList
et fondé sur l'indice des opérations de ce type sont généralement réservés pourList
s. UnTreeSet
est plus approprié pour des choses comme trouver le plus proche de l'élément contenu qui est >= une certaine valeur.Une chose que vous pourrait faire si la manière la plus rapide possible de l'accès à la k-ième plus petit élément ont été vraiment important serait d'utiliser un
ArrayList
plutôt qu'unTreeSet
et gérer les insertions en binaire de la recherche pour le point d'insertion et de insérant l'élément à l'index ou le remplacement de l'élément existant à l'index, en fonction du résultat de la recherche. Ensuite, vous pourriez obtenir la k-ième plus petit élément en O(1) par appeler justeget(k)
.Vous pouvez même créer une mise en œuvre de
SortedSet
qui gère tout ce qui et ajoute laget(index)
méthode si vous avez vraiment voulu.Utilisation TreeSet.iterator() pour obtenir un itérateur dans l'ordre croissant et l'appel
next()
K fois:J'ai eu le même problème. Alors j'ai pris le code source de java.util.TreeMap et écrit IndexedTreeMap. Il implémente mon propre IndexedNavigableMap:
La mise en œuvre est basée sur la mise à jour du nœud de poids dans le rouge-noir arbre lorsqu'il est modifié. Le poids est le nombre de nœuds enfants en dessous d'un nœud donné, en plus de soi - même. Par exemple, lorsqu'un arbre est tourné vers la gauche:
updateWeight simplement les mises à jour des poids jusqu'à la racine:
Et quand nous avons besoin de trouver l'élément à l'index ici est la mise en œuvre qui utilise des pondérations:
Également très pratique de trouver l'indice d'une clé:
Vous pouvez découvrir le résultat de ce travail à http://code.google.com/p/indexed-tree-map/. Déplacé à https://github.com/geniot/indexed-tree-map
[Ci-dessous, j'ai abréger "k-ième plus petit élément opération de recherche" comme "Kth op."]
Vous avez besoin de donner plus de détails. Les opérations qui feront de votre structure de données fournir? est K dans Kth opération très petite par rapport à N, ou peut-il être quelque chose? Combien de fois allez-vous avoir des insertions & les suppressions par rapport à regarder ups? Combien de fois aurez-vous Kth plus petit élément de recherche par rapport à regarder ups? Vous êtes à la recherche pour une solution rapide, de quelques lignes à l'intérieur de bibliothèque Java, ou êtes-vous prêt à dépenser de l'effort de construire une structure de donnée spécifique?
Les opérations de fournir pourrait être n'importe quel sous-ensemble de:
De recherche (trouver un élément par sa clé; où la clé est comparable et peut être n'importe quoi)
Insérer
Supprimer
Kth
Voici quelques possibilités:
Si il n'y aura pas ou très peu d'insertions&les suppressions, vous pouvez trier les éléments et utiliser un tableau, avec O(Log(N)) regard du temps et de l' O(1) pour Kth.
Si O(Log(N)) pour de Recherche, Insérer, Supprimer et O(k) pour Kth op. est assez bonne, probablement le plus facile la mise en œuvre serait Ignorer les Listes. (Article de Wikipedia est très bien si vous avez besoin de plus de détails)
Si K est assez petit, ou Kth opérations ne viendra après "insertions&les suppressions de phase" vous pouvez garder le plus petit K éléments dans un segment, tri après les insertions&les suppressions de O(N + k Log k) temps. (Vous aurez besoin également d'une salle de Hachage pour de Recherche)
Si K est arbitraire et O(N) est assez bon pour Kth opération, vous pouvez utiliser une table de Hachage pour O(1) temps de recherche, et l'utilisation d'un "one-sided-QuickSort" l'algorithme pour Kth opérations (l'idée de base est de faire un tri rapide, mais dans tous les binaires diviser recurse seulement sur le côté vous avez vraiment besoin; ce qui donnerait (ce qui est une grossière simplification) N (1/2 + 1/4 + 1/8 + ... ) = O(N) temps prévu)
Vous pouvez construire un Augmentée "simple" Intervalle de structure de l'Arbre dont chaque nœud de garder le nombre de ses enfants, de sorte que de Recherche, Insérer, Supprimer, Kth tout calculer en O(Log N) temps tant que l'arbre est équilibré, mais peut-être qu'il ne serait pas difficile à mettre en œuvre si vous êtes un novice.
etc. etc. L'éventail de possibilités est infini comme les interprétations possibles de votre question.
Pourriez-vous utiliser un ConcurrentSkipListSet et l'utilisation de la méthode toArray ()? ConcurrentSkipListSet est triée selon l'ordre naturel des éléments. La seule chose que je ne suis pas sûr de savoir si le toArray() est O(n) ou depuis qu'il est soutenu par une Liste (soutenu par un tableau, comme ArrayList) il est O(1).
Si toArray() est O(1) l', vous devriez être en mesure d'être un skipList.toArray()[k] pour obtenir la k-ième plus petit élément.
Je sais que cette question est assez vieux, mais depuis TreeSet implémente NavigableSet vous avez accès à l'ensemble de la méthode qui s'exécute en temps constant.
La première() qui prend log(n) le temps où n est la taille de l'ensemble original. Ce n'est pas sans créer certains objets inutiles qui pourraient être évités avec une plus forte mise en œuvre de TreeSet, mais il évite l'utilisation d'un tiers de la bibliothèque.