Quel est l’algorithme le plus rapide pour sélectionner le kème plus grand nombre dans un tableau non sortingé contenant des éléments non uniques?

Dupliquer possible:
Comment trouver le kème élément le plus grand dans un tableau non sortingé de longueur n dans O (n)?

Le nombre d’éléments peut varier de 1 à 10 millions. Quel est l’algorithme de sélection le plus rapide disponible à cet effet? Veuillez noter que les structures de données telles que AVL Trees ne fonctionneront pas ici en raison de la duplication d’éléments de tableau.

Un algorithme de sélection peut s’exécuter en temps O (N).

La méthode la plus générale consiste à effectuer un passage dans le tableau en conservant le nombre K le plus grand que vous ayez vu jusqu’à présent. Renvoie le dernier élément de cette liste. Comme @ChrisA le souligne dans les commentaires, std::nth_element (documenté ici ) est le moyen le plus rapide d’utiliser cette approche.

Si vous souhaitez toujours que les K plus grands éléments soient les plus importants (et que les données soient parfois modifiées), envisagez de stocker les données dans un segment de mémoire. Cela coûte plus cher, mais vous donne une structure “en direct” des données.

Cela peut être fait au moment de la compilation avec ce code (gardez à l’esprit que vous avez besoin de la dernière version de GCC ou de Clang, cela ne fonctionnera pas dans MSVC2k12 pour le moment). Cela rend la compilation lente mais est instantanée au moment de l’exécution.

 #include  constexpr int array[10] = { 1, 0, 2, 3, 0, 2, 7, 1, 9, 2 }; template struct find_biggest_r { enum { value = find_biggest_r<(array[index] > maxest ? array[index]:maxest),index-1>::value }; }; template struct find_biggest_r { enum { value = (array[0] > maxest ? array[0] : maxest) }; }; template struct find_biggest { enum { value = find_biggest_r::value }; }; int main() { std::cout << find_biggest<10>::value; } 

EDIT: Désolé, c’était pour le plus grand. Pour le kème plus grand, je dois append un argument ou deux, je le ferai plus tard aujourd’hui.