Algorithme d'entretien d'embauche?

Question

MISE À JOUR: Quelqu'un peut-il s'il vous plaît répondre à mon dernier commentaire sur n. «pronoms» m. réponse?

Remarque: j'ai déjà posé cette question mais c'était un désordre complet, donc je l'écris avec plus de détails et dans la forme originale.

Question:

Je gère un système de vote entre N participants (chacun indexé de 1 à N) où je souhaite prendre en charge les fonctions suivantes:

1. Init (N) - Initialise la structure de données. -O (1)
2. Vote (j, i) - Ajoutez au tableau des résultats que la personne j a voté (exactement 1) pour la personne i - où il n'est pas permis à quelqu'un de voter lui-même. -O (1)
3. Électeurs (i) - Renvoyez le nombre de personnes ayant voté à i. -O (1)
4. Origine (j) - Renvoie le nombre de votes que la personne j a donnés aux autres. -O (1)
5. Favoris (k) - Imprimez les meilleurs participants (par ordre décroissant) en fonction du nombre de votes obtenus. -D'accord)
6. Évité () - Imprimez tous les participants qui n'ont pas obtenu de vote. -O (r) où r est le nombre de participants imprimés

Dans cette question , la complexité de l'espace doit être O (N) .

Autorise uniquement l'utilisation de tableaux et de listes (doublement) liées.

---

Ce que j'ai fait? J'ai résolu 1-4 si facilement simplement en déclarant un tableau dont la taille est N et chaque cellule contient des valeurs; gotet sent. quand les ivotes pour jj'augmente ont une valeur jet une valeur envoyée pour iun.

Pourtant, je n'ai aucune idée sur la façon de résoudre 5 et 6 dans la complexité requise.

Remarque: je recherche l'algorithme / l'idée plutôt qu'un code réel.

Answer 1

Notez que pour chaque opération, le candidat qui a été voté a augmenté son score d'exactement un.

Cela ouvre une nouvelle stratégie - plutôt que de mapper un candidat à son score, mappez un score à la liste des candidats avec ce score.

Cela peut être implémenté tout simplement sous la forme d'une liste de listes candidates: (dans un modèle comme la syntaxe:) list<list<Candidate>>.

De plus, gardez un tableau mappant chaque numéro candidat au pointeur de l' Candidateélément réel .

La liste des candidats avec 0, sera implicitement définie sur tous les candidats initialement, de la même manière que vous initialisez un tableau dans O (1) .

• Lorsqu'un vote est émis:

1. Vous trouvez le candidat à partir de la référence: O (1)
2. Vous le supprimez de sa liste actuelle et l'ajoutez à la liste suivante: O (1)
3. Pour prendre Avoided()en charge dans O(r): Si le nombre d'éléments dans la liste "0" est inférieur à la moitié, changez-la pour qu'elle soit une liste régulière à la place.
4. Si l'élément précédent représentant un score n'a plus de candidats, supprimez-le et liez directement le score précédent au suivant (c'est-à-dire si aucun candidat avec le score 3, connectez-vous 2<->4) O(n).

• Obtenir topK est maintenant facile et fait en O(k)itérant la liste des scores de la fin au début (arrêt après la sortie des kcandidats)
• O(n) = O(r)On évite désormais si plus de la moitié des candidats ont été évités, ou O(r)sinon grâce à l'optimisation (3) en insertion.

Answer 2

Voici une autre façon d'implémenter Avoided (). Associez deux numéros à chaque personne qui a été votée, le début et la fin de la course. Au départ, tous les éléments sont définis sur None(peut être fait avec l'astuce d'initialisation du tableau O (1)).

Lorsque la personne mest votée pour la première fois, mettez à jour startOfRunet endOfRunarrays:

if startOfRun[m-1] != None and startOfRun[m+1] == None
   endOfRun[startOfRun[m-1]] = m
else if startOfRun[m-1] == None and startOfRun[m+1] != None
   startOfRun[endOfRun[m+1]]
else if startOfRun[m-1] != None and startOfRun[m+1] != None
   endOfRun[startOfRun[m-1]] = endOfRun[m+1]
   startOfRun[endOfRun[m+1]] = startOfRun[m-1]
else
   startOfRun[m] = m
   endOfRun[m] = m

(conditions de bord omises par souci de concision).

Maintenant, vous avez des séries de personnes qui ont été votées, et vous pouvez facilement aller du début à la fin de chaque course. Les chiffres à l'intérieur des pistes sont tous faux, mais nous ne nous soucions pas d'eux. Il y a des courses O (r) afin que vous puissiez ignorer tous ceux qui ont été votés pour O (r).

---

Voici une autre manière d'implémenter Favored (). Avoir deux tableaux, (1) un tableau en expansion de personnes triées par score, et (2) une carte d'un score à l'index de la dernière personne dans le premier tableau ayant un score non inférieur à cela (s'il n'y en a pas, alors None) . Au départ, le premier tableau est vide et le second contient Nones. Exemple:

(array 1)
(index)       1 2 3 4 5 6 7 8 9
person        3 6 5 1 4 2 8 9 7
score         7 7 7 5 5 3 2 2 2

(array 2)
score         1 2 3 4 5 6 7 8 9
index in 1st  9 9 6 5 5 3 3 - -

Une fois qu'une personne est votée pour la première fois, elle est ajoutée à la fin du tableau avec le score de 1 et array2[1]est mise à jour. Une fois que la personne est à nouveau votée, elle est échangée avec la première personne du tableau ayant le même score, le score est augmenté et le second tableau est mis à jour (il suffit de mettre à jour un élément, celui qui correspond au nouveau But).