C#:Эффективный алгоритм поиска наибольших m элементов в матрице N x N

Question

Я хотел бы знать, существует ли эффективный алгоритм для поиска наибольших m элементов в матрице N x N, с заголовком метода, подобным этому:

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

Есть какие-нибудь идеи?

Answer 1

Если вы рассматриваете матрицу N x N как массив из N x N элементов, вы можете применить один из следующих методов:

Прямое применение алгоритма выбора на основе быстрой сортировки Быстрый алгоритм выбора на основе сортировки может быть использован для поиска k наименьших или k наибольших элементов.Чтобы найти k наименьших элементов найдите k-й наименьший элемент, используя алгоритм быстрой сортировки на основе медианы медиан .После разбиения, которое находит k-й наименьший элемент, все элементы, меньшие, чем k-й меньший элемент, будут присутствовать слева к k-му элементу и всем элементам более крупным будет присутствовать непосредственно к k-му наименьшему элементу.Таким образом, все элементы от 1-го до k-го элемента включительно составляют k наименьших элементов.Временная сложность линейна по n, общему количеству элементов.

Решения, основанные на структуре данных Другой простой метод заключается в добавлении каждого элемента списка в упорядоченную заданную структуру данных, такую как куча или самобалансирующееся бинарное дерево поиска, состоящее не более чем из k элементов.Всякий раз, когда структура данных содержит более k элементов, мы удаляем самый большой элемент, что может быть сделано за O (log k) времени.Каждая операция вставки также занимает O (log k) времени, что приводит к Общему времени O (nlog k).

Можно преобразовать список в кучу за Θ(n) времени, а затем обойти кучу, используя модифицированный Алгоритм поиска по ширине, который присваивает элементам приоритет Очередь (вместо обычной очереди , которая обычно используется в BFS), и завершите сканирование после обхода ровно k элементов.Поскольку размер очереди остается O (k) на протяжении всего обхода, для завершения потребуется O (klog k) времени, что приведет к ограничению по времени O (n + klog k) для этого алгоритма.

От здесь.