C #: algorithme efficace pour trouver les plus grands m éléments dans une matrice N x N

Question

Je voudrais savoir s'il existe un algorithme efficace pour trouver les m plus grands éléments dans une matrice N x N, avec un en-tête de méthode comme celui-ci:

double[] greatestValues(double[][] matrix, int numberOfElements);

Des idées?

Answer 1

Si vous traitez la matrice N x N comme un tableau de N x N éléments, vous pouvez appliquer l'une des techniques suivantes:

  

Application directe de l'algorithme de sélection rapide basé sur le tri   algorithme de sélection basé sur le tri peut être   utilisé pour trouver k plus petit ou k plus grand   éléments. Pour trouver k plus petits éléments   trouver le kème plus petit élément en utilisant   la médiane du tri rapide des médianes   algorithme. Après la partition   trouve le kème plus petit élément, tout   les éléments plus petits que le kth   élément plus petit sera présent à gauche   au kième élément et à tous les éléments   plus grand sera présent droit à la   kth plus petit élément. Donc tout   éléments du 1er au kième élément   inclus constituent le k le plus petit   éléments. La complexité temporelle est   linéaire en n, le nombre total de   éléments.

     

Solutions basées sur la structure de données Une autre méthode simple consiste à ajouter chaque solution.   élément de la liste dans un ordre   définir la structure de données, telle qu'un tas ou   arbre de recherche binaire auto-équilibrant,   avec au plus k éléments. Chaque fois que le   la structure de données a plus de k   éléments, on enlève le plus grand   élément, ce qui peut être fait en O (log k)   temps. Chaque opération d'insertion aussi   prend O (log k) temps, résultant en   O (nlog k) temps global.

     

Il est possible de transformer la liste   dans un tas dans (n) temps, puis   traverser le tas en utilisant un modifié   Largeur premier algorithme de recherche qui   place les éléments dans une priorité   File d'attente (au lieu de la file d'attente ordinaire   qui est normalement utilisé dans un BFS), et   terminer le scan après avoir traversé   exactement k éléments. Comme la taille de la file d'attente   reste O (k) tout au long du parcours,   il faudrait O (klog k) temps pour   complète, conduisant à un délai de   O (n + klog k) sur cet algorithme.

De ici .