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
0
user8959288 17 nov. 2017 à 21:09

4 réponses

Meilleure réponse

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 < à >.

3
Jim Mischel 18 nov. 2017 à 04:15

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.

0
DomainFlag 17 nov. 2017 à 19:37
  1. Triez le tableau et prenez les X premiers éléments
  2. Utilisez la fonction max de votre langage pour trouver le plus grand élément. Extrayez-le du tableau. Répétez X fois.
1
Prune 17 nov. 2017 à 18:13

Vous pouvez créer un tas min et appeler la fonction ExtractMin (len (arr) - x) fois pour obtenir la Xème plus grande valeur.

1
harshil9968 17 nov. 2017 à 18:16
47356807