J'ai un tableau: [2, 4, 5, 1, 4, 20]
Comment obtenir les valeurs X les plus élevées de ce tableau?
Comme ça:
getHighest(2): 25, 5
getHighest(3): 25, 5, 4
4 réponses
L'idée de base est de créer une file d'attente prioritaire (tas max) des X premiers éléments. Ensuite, pour chaque élément restant dans le tableau, s'il est plus petit que le premier élément du tas, supprimez le premier élément du tas et ajoutez le nouvel élément. Quelque chose comme ça:
heap = new maxHeap();
for (i = 0; i < X; i++)
{
heap.Add(a[i]);
}
for (; i < a.Length; ++i)
{
if (a[i] < heap.peek())
{
heap.removeFirst();
heap.Add(a[i]);
}
}
// at this point, the smallest X items are on the heap.
// Remove them:
while (!heap.IsEmpty())
{
print(heap.removeFirst());
}
Notez que ce que je décris ci-dessus est comment obtenir les X plus petits éléments du tableau. Si vous voulez que le X soit le plus grand, créez un tas min et changez la comparaison de < à >.
Une implémentation naïve de C ++ trie le tableau en ordre décroissant par algorithme de tri rapide comme dans l'exemple ci-dessous:
void swapArray(int * tab, int ind1, int ind2) {
int swap = tab[ind1];
tab[ind1] = tab[ind2];
tab[ind2] = swap;
}
int sortArray(int * tab, int min, int max) {
int pivot = max;
bool leftSwapping = true;
while(min < max) {
if(leftSwapping) {
if(tab[min] < tab[pivot]) {
swapArray(tab, min, pivot);
pivot = min;
max--;
leftSwapping = false;
} else {
min++;
}
} else {
if(tab[max] > tab[pivot]) {
swapArray(tab, max, pivot);
pivot = max;
min++;
leftSwapping = true;
} else {
max--;
}
}
}
return pivot;
}
void quickSort(int * tab, int min, int max) {
if(min < max) {
int pivot = sortArray(tab, min, max);
quickSort(tab, min, pivot-1);
quickSort(tab, pivot+1, max);
}
};
Et vous pouvez boucler autant de valeurs dont vous avez besoin hors du tableau. Remarque: que QuickSort n'est pas un algorithme stable, le tri par fusion et le tri par insertion peuvent donc être utiles dans ce cas en fonction de votre cause. C'est dans le cas où vous souhaitez utiliser plusieurs fois la fonction getHighest, sinon utilisez simplement le tri par sélection simple et prenez autant de valeurs que vous le souhaitez.
- Triez le tableau et prenez les
Xpremiers éléments - Utilisez la fonction
maxde votre langage pour trouver le plus grand élément. Extrayez-le du tableau. RépétezXfois.
Vous pouvez créer un tas min et appeler la fonction ExtractMin (len (arr) - x) fois pour obtenir la Xème plus grande valeur.
Questions connexes
De nouvelles questions
algorithm
Un algorithme est une séquence d'étapes bien définies qui définit une solution abstraite à un problème. Utilisez cette balise lorsque votre problème est lié à la conception d'un algorithme.