C #: Algoritmo Eficiente para encontrar maiores m elementos em uma matriz de N x N

Question

Gostaria de saber se há um algoritmo eficiente para encontrar as maiores m elementos em um N x matriz N, com um cabeçalho de método como este:

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

Todas as idéias?

Answer 1

Se você tratar a N x matriz N como uma matriz de N x N itens que você pode aplicar uma das seguintes técnicas:

A aplicação direta da seleção rápida baseada espécie algoritmo A rápida tipo algoritmo de seleção de base pode ser usado para encontrar k menor ou maior de k elementos. Para encontrar k menores elementos encontrar o enésimo menor elemento usando a mediana das medianas rápida baseada espécie algoritmo. Após a partição que encontra o enésimo menor elemento, todos os elementos mais pequenos do que o de ordem k menor elemento estará presente esquerda ao elemento k e todos elemento maior estará presente certo para o KTH menor elemento. assim, todos elementos do 1º ao elemento k inclusive constituem o k menor elementos. A complexidade de tempo é linear em n, o número total de elementos.

soluções

Estrutura de dados baseados Outro método simples é adicionar cada elemento da lista em um ordenado estrutura de dados do conjunto, tal como uma pilha ou auto-equilíbrio árvore de busca binária, com a maioria dos elementos de k. sempre que o estrutura de dados tem mais do que k elementos, nós removemos o maior elemento, que pode ser feito em O (log K) Tempo. Cada operação de inserção também leva O (log K) do tempo, resultando em O (nlog k) tempo total.

É possível transformar a lista num montão no T tempo (n), e, em seguida atravessar a pilha usando uma versão modificada Em largura de pesquisa algoritmo que coloca os elementos em uma prioridade Fila (em vez da fila comum que é normalmente utilizado numa BFS), e terminar a varredura depois de atravessar exatamente k elementos. À medida que o tamanho da fila permanece O (k) ao longo do percurso, isso exigiria O tempo para (klog k) completa, levando a um tempo ligado da O (n + k klog) sobre este algoritmo.

A partir aqui .