Comment trouver «n» positions d'éléments les plus volumineuses dans une matrice 2D? Existe-t-il un bon algorithme, autre que la force brute?Recherche de n positions d'éléments les plus volumineuses dans une matrice 2D
Merci
Vous pouvez trouver les n plus éléments (et leurs positions) dans un tableau à deux dimensions de manière aussi efficace que possible dans un tableau à une dimension.
Il existe a variety of selection algorithms qui s'exécute en temps linéaire. Quickselect a une complexité de temps moyenne linéaire mais, comme Quicksort, peut être quadratique dans le pire des cas. L'algorithme médian-of-medians a à la fois une complexité de temps linéaire attendue et la pire des cas.
Bien sûr, si les éléments sont triés, alors c'est trivial: allez à la fin du tableau et sélectionnez le nombre d'éléments requis à partir de là. Cela peut prendre un peu de logique en fonction de la façon dont le tableau est trié en deux dimensions, mais ce n'est pas difficile.