La question est la suivante: Chaque année, je reçois les grades N (pas de nombres discrets 0-100),Comment puis-je le faire en temps linéaire pour chaque année?
A. Je dois trouver la note maximale pour l'année. B. À la fin de l'année N, je dois retourner les N plus hautes notes de toutes les années N2 de toutes les N années.
T (i) est l'exécution de l'algorithme au cours de l'année i.
I nécessité de proposer une structure algorithme/données qui fera A & hôte à MAX (T (1), T (2), ..., T (N)) = O (N). (Travail linéaire chaque année)
Une solution dans O (NlogN) est la plus basse que j'ai obtenue en maintenant un maximum de N catégories maximales de chaque année et tas maximum pour chaque année, et supprimer min et insérer la suivante en ligne à partir de quelle année nous avons supprimé.
Merci pour votre aide!
Vous avez pas d'ordre d'aucune sorte? Je ne vois pas comment vous pouvez éviter de regarder au moins une fois toutes les notes N^2 alors ... Je ne vois même pas votre O (N log N) travailler. –
@JeanLogeart chaque année l'algorithme reçoit N grades, et doit les traiter en O (N). –