Je dois concevoir une structure de données capable de supporter efficacement les opérations suivantes sur une séquence de numéros stockée (à la fois adaptée):
x au premier i éléments de la séquence
- Ajoute un entier
k à la fin de la séquence
- Retirez le dernier élément de la séquence
- récupérez la moyenne de tous les éléments de la séquence
Exemple
commençant par une séquence vide []
- Ajoutez 0 (
[0] )
- ANNEXE 5 (
[0, 5] )
- APPEND 6 (
[0, 5, 6] )
- ajoutez 3 aux 2 premiers éléments de la séquence (
[3, 8, 6] )
- récupérez la moyenne 5.66 (
[3, 8, 6] )
- Retirez le dernier élément (
[3, 8] )
- récupérez la moyenne de 5,5 (
[3, 8] )
Travail précédent
J'ai pensé à utiliser Fenwick Arbres ( Topcoder éditorial ) Mais pour cela, je devrais spécifier la taille maximale de la séquence de l'initialisation de l'arborescence de Fenwick qui est ne sais pas nécessairement. Mais si j'ai un nombre maximum d'éléments que la séquence peut prendre en charge, je peux prendre en charge ces opérations sur O (lg n) si je sauvegardez également la somme de tous les éléments de la séquence.
edit: La question concerne un problème de codeforces et j'ai besoin d'une durée de fonctionnement sous-linéaire pour toutes les opérations et que l'ajout aux premiers éléments peut être, dans le pire des cas, être identique à l'ajout à toute la séquence
6 Réponses :
Avez-vous envisagé d'utiliser une liste liée plus la longueur et la somme en cours? Pour chaque opération, vous pouvez maintenir la moyenne actuelle avec un travail supplémentaire constant (vous connaissez la longueur de la liste et la somme, et toutes les opérations changent ces deux valeurs de manière constante).
La seule opération non constante ajouterait Une constante à un préfixe arbitraire, qui prendrait du temps proportionnelle à la taille du préfixe, car vous auriez besoin d'ajuster chaque nombre.
pour faire de toutes les opérations constants (amortizé) constante nécessite plus de travail. Au lieu d'utiliser une liste doublement liée, appuyez sur la matrice avec une pile. Chaque fente APPEND 0: APPEND 5: annexe 6: Ajoutez 3 aux 2 premiers éléments de la séquence: récupération de la moyenne 5.66 retirez le dernier élément récupération de la moyenne 5.5 retirez le dernier élément Voici un code Java qui illustre l'idée peut-être plus clairement: i dans la matrice contient maintenant le numéro du numéro de i et la constante à ajouter à chaque élément jusqu'à i . (Notez que si vous dites "Ajoutez 3 à chaque élément jusqu'à l'élément 11," Slot 11 contiendrait le nombre 3 mais les machines à sous 0-10 seraient vides.) Toutes chaque opération est aussi auparavant, sauf que l'ajout d'un nouvel élément Implique le truc de doublage de la matrice standard et lorsque vous allez le dernier élément de la fin de la file d'attente, vous devez ajouter (A) ajouter dans la constante à cette fente, et (B) Ajoutez la valeur constante du logement i < / code> à la constante pour la fente i-1 . Donc, pour votre exemple: [(0,0)], somme 0, longueur 1 ([ (0,0), (5,0)], somme 5, longueur 2 [(0,0), (5,0), (6 , 0)], somme 11, longueur 3 [(0,0), (5,3), (6 , 0)], somme 17, longueur 3 [(0,0), (5,3 )], somme 11, longueur 2 [(0,3)], somme 3, longueur 1
Je préférerais si toutes les opérations sont au moins logarithmiques car le préfixe pourrait être la longueur d'une très grande liste. Quel serait le travail supplémentaire pour le rendre constant?
@Gustavotorres, je peux manquer quelque chose, mais je ne vois pas comment ajouter quelque chose à i éléments de la liste pourrait être inférieur à o (i)
L'astuce consiste à le faire paresseusement, en s'appuyant sur le fait que le seul moyen de observer les valeurs de la file d'attente consiste à les renvoyer ou à prendre leur moyenne. Voir l'échantillon de code.
@jacobm Très belle mise en œuvre! Simple et efficace! Merci!
Solution intéressante, bien que l'ajout d'un élément à la liste des matrices pourrait prendre une heure (N) (quand elle doit se développer). Je me demande si cela est compté. . .
Droite, c'est pourquoi j'ai dit amorti constant plutôt que vraie constante. La bonne nouvelle est que toute séquence de n ajouts prendra au plus un temps constant N étapes.
@Jimmischel mais si nous utilisons deux piles au lieu d'arraylist pour éléments et ajoutéConstants , nous pouvons vraiment obtenir un temps constant en supposant que la pile soit implémentée avec une liste (ce qui est généralement le cas )
@Gustavotorres, mais comment obtiendriez-vous la mise à jour de temps constante des éléments arbitraires dont vous avez besoin pour ajouter à un préfixe arbitraire?
@jacobm Oui, j'ai négligé ça. Il est certainement préférable d'obtenir le temps constant amorti. Même utiliser des dictionnaires, nous allons toujours obtenir une heure constante amortie
Cette structure de données peut simplement être un tuple (n, s) où n est le nombre et S est la somme et une pile de nombres. Rien d'extraordinaire. Toutes les opérations sont O (1) sauf pour le premier qui est O (i).
sonne comme un Liste doublement liée avec la maintenance de la tête et de la référence de la queue, ainsi que le somme et comptage actuels.
Ajoutez l'entier X au premier I ÉLÉMENTS DE LA SÉQUENCE
Démarrer sur * Head, ajoutez
x , élément suivant. Répétezi fois.somme + = i * xAjoute un entier K à la fin de la séquence
Démarrer à la queue *, créez un nouvel article avec la tête = la queue, la queue = null. Mise à jour * queue, somme et compte en conséquence.
Retirez le dernier élément de la séquence
mise à jour * queue à * tail-> prev. Mettre à jour la somme, décompte compte
récupérer la moyenne de 5,5 ([3, 8])
Retour Somme / Nombre
+1 Bien que vous puissiez le faire avec une liste individuelle. Pas besoin de la double liaison. Gardez simplement la tête et les pointeurs de la queue.
Sans lien vers l'élément précédent, supprimer le dernier élément devient O (n), non? Dois savoir quoi mettre à jour * queue à
Non, vous avez besoin des deux - vous devez être capable de trouver le prochain temps constant et vous devez être capable de se déplacer sur un préfixe de taille arbitraire dans le temps proportionnel à la taille du préfixe.
Ahh, tu as raison. Dois avoir ce lien de retour pour supprimer le dernier.
"Répéter I fois" est O (n), a-t-il déclaré qu'il avait besoin de sous-vêtements.
@ROBERTKING YEAH C'était une modification après avoir répondu. Honnêtement, je ne suis pas sûr que cela soit encore possible, d'aller mieux que o (i) pour cette opération au moins. Je ne comprends pas ce que cela signifierait même
Vous pouvez utiliser un arbre indexé binaire (journal (n)). Une autre option est de répondre à plusieurs requêtes à la fois. Par exemple. Si vous avez les paires suivantes (i, x) = (1,1), (2, 1), (3, 1), vous passerez ensuite à 1, 2, 3 ne faisant que 3 opérations plutôt que 3 + 2 + 1 Opérations. (mauvais exemple mais ouais).
Le rond n ° 174 des postes de problèmes ont publié un éditorial pour ce tour. Vous pouvez le trouver ici . Vous pouvez également jeter un coup d'œil sur certaines solutions acceptées: python , C ++ .
Bien sûr, la solution optimale ici est O (1) pour chaque opération. Je pourrais essayer de l'expliquer plus à fond, si vous ne comprenez toujours pas, mais je pense que les solutions données sont assez simples.
J'ai lu le tutoriel mais leur explication n'était pas très claire pour moi, et la plupart des solutions étaient assez cryptiques. Bien que la solution python soit très belle en effet
Je vous suggère d'essayer d'utiliser un arbre indexé binaire .
Ils vous permettent d'accéder à la fréquence cumulative dans O (log (n)).
Vous pouvez également ajouter au premier i éléments I dans le journal de commande (I).
Cependant, au lieu d'augmenter les premiers i éléments de X, augmentez simplement l'élément N-ITH par x.
Pour enlever le dernier élément, peut-être avoir un autre arbre qui ajoute à quel point l'élimination cumulative a été supprimée. (Ainsi, au lieu de supprimer, vous ajoutez ce montant à un autre arborescence que vous souscrivez toujours à votre résultat lors de l'accès au premier arbre).
Pour Ajout, je vous suggère de commencer par un arbre de taille 2 * N cela vous donnera de la place. Ensuite, si vous obtenez déjà plus de 2 * N, ajoutez un autre arbre de taille 2 * n. (Pas exactement sûr de la meilleure façon de le faire, mais j'espère que vous pourrez le comprendre).
Donc, au lieu d'augmenter les premiers i éléments de X, vous augmentez l'élément ith par x i? Mais que se passe-t-il si c'est le dernier élément de la liste, puis vous le supprimez? Vous perdez i X, quand vous n'étiez vraiment pas censé perdre x + quel que soit le dernier élément. La somme est alors incorrecte.
Vous augmentez l'élément Nth-i par x. Cela augmente la fréquence cumulative des éléments N-I, N-I + 1, .. n par x. La somme effective est la somme des fréquences cumulatives, mais c'est O (1) si vous en suivez le sien.
Pour satisfaire la première exigence, vous pouvez maintenir une structure de données distincte d'ajout d'opérations. Fondamentalement, c'est une collection ordonnée de gammes et d'incréments. Vous maintenez également la somme de ces ajouts. Donc, si vous avez ajouté 5 aux trois premiers articles, puis ajoutez 12 aux 10 premiers articles, vous auriez:
key: 3 value: 5 key: 10 value: 12
De quoi s'agit-il? Cette première opération est inhabituelle.
J'essaie de résoudre un problème sur Codeforces depuis un certain temps, mais je pourrais juste Utilisez l'arbre mais la solution était apparemment trop lente en raison de l'initialisation de la matrice de l'arbre (je pense)