Algorithme pour trouver les nombres hauts / bas avec au plus 1.5n comparaisons
J'ai pensé à cette devoirs question pour un peu maintenant. Compte tenu d'un certain nombre de tableau de taille n, la conception d'un algorithme qui permettra de trouver de la haute et de et de faibles valeurs d'au plus 1,5 n comparaisons.
Mon premier essai était
int high=0
int low= Number.MaxValue //problem statement is unclear on what type of number to use
Number numList[0 . . n] //number array, assuming unsorted
for (i=0, i < n, i++) {
if (numList[i] > high)
high = numList[i]
else if (numList[i] < low)
low = numList[i]
}
Mon problème est que chaque itération de la boucle a l'une des trois possibilités:
- de faible valeur est trouvé - 1 comparaison faite
- haute valeur est trouvé - 2 comparaisons
- n'est trouvé - 2 comparaisons
Donc pour un tableau d'ensemble de la traversée, un maximum de 2n comparaisons peuvent être faites, ce qui est loin d'être le problème exigence maximum de 1,5 n comparaisons.
source d'informationauteur Jason
Vous devez vous connecter pour publier un commentaire.
Commencer avec une des paires de nombres et à trouver les min et max (n/2 comparaisons). Ensuite, savoir global maximum de n/2 locaux maximise (n/2 comparaisons), et de la même façon globale min de locaux minutes (n/2 comparaisons). Total des comparaisons: 3*n/2 !
Noter que la solution ci-dessus modifications de la matrice. Solution de rechange:
Je sais que cela a déjà été répondu, mais au cas où quelqu'un est à la recherche d'une autre façon de penser à ce sujet. Cette réponse est similaire à De Lestermais peut-poignée impair de valeurs de n sans casser et toujours à plus de 1,5 n comparaisons. Le secret est dans le module. 😉
Comme un des effets secondaires de s'assurer que nous la dernière valeur dans la bonne sous-tableau, le deuxième élément dans la givenList seront comparés et mis deux fois. Cependant, puisque nous ne sommes pas changer le tableau d'origine et nous nous sommes seulement intéressés dans le haut et le bas de l'ensemble, cela n'a pas vraiment faire une différence.
C'est la même réponse que ElKamina mais comme j'avais déjà commencé à écrire le pseudo-code je pensais le finir et de le poster.
L'idée est de comparer paires de valeurs (n/2 comparaisons) pour obtenir un tableau de valeurs élevées et un tableau de valeurs faibles. Avec chacun de ces tableaux, nous avons à nouveau comparer des paires de valeurs (2 * n/2 comparaisons) pour obtenir la plus haute et la plus basse des valeurs respectivement.
Voici le pseudo-code:
Ce code ne tient pas compte de
n
n'étant pas encore ou la table initiale étant vide.C'est une question que j'ai eu lors d'une interview et j'ai trouvé la réponse avec un petit soupçon de l'interviewer qui était "Comment voulez-vous comparer deux nombres?" (il a vraiment aidé).
Voici l'explication:
Permet de dire que j'ai 100 numéros (vous pouvez facilement le remplacer par n, mais il fonctionne mieux pour l'exemple, si n est un nombre pair). Ce que je fais, c'est que j'ai divisé en 50 listes de 2 nombres. Pour chaque couple je faire une comparaison et je me suis fait (ce qui fait 50 comparaisons maintenant) ensuite, j'ai juste à trouver le minimum des minimums (49 comparaisons) et le maximum des maximums (49 comparaisons ainsi), de sorte que nous avons à faire 49+49+50=148. Nous y sommes !
Remarque: pour trouver le minimum que l'on procéder comme suit (en pseudo-code):
Et on la retrouve dans (n-1) comparaisons. Le code est presque le même pour le maximum.