Как вывести 5 наибольших элементов матрицы с их индексами?

Question

[Steve Gorton]

Вывести 5 наибольших элементов матрицы с их индексами, вот только не знаю как это реализовать, хотя бы идею

for (int i = 0; i < 5; ++i)
    {
        int temp_max_value = 0;
        for (int j = 0; j < row; ++j)
        {
            for (int k = 0; k < column; ++k)
            {
                if(matrix[j][k] > temp_max_value)
                {
                    temp_max_value = matrix[j][k];
                }
            }
        }
        printf("Max value %d\n", temp_max_value);
    }

Answer 1

[Рональд Макдональд]

Идея: найти наибольшее число каждой строки, загнать их в отдельный массив, отсортировать по возрастанию и взять пять крайних чисел.

Comments

[Steve Gorton]

Я тоже так думал, но что делать, если в матрице количество строк меньше 5?

[Rsa97]

А если все наибольшие числа в одной строке?

[Рональд Макдональд]

Steve Gorton, Rsa97, хм.

Ну тогда загнать матрицу в одномерный массив и отсортировать уже её. Топорно, прожорливо, но работает.

Ещё более топорно - просканировать массив пять раз, находя каждый раз наибольшее число, исключая те, что уже найдены.

Answer 2

[Rsa97]

Берёте три массива по пять элементов, в первом будет сами числа, во втором и третьем - индексы. Инициализируете массивы индексов значениями -1.
Обходите всю матрицу и для каждого элемента матрицы проверяете все элементы массива. Если в массиве есть элемент с индексами -1 или значение в массиве меньше, чем элемент матрицы, то записываете в массив значение из матрицы с его индексами.

Answer 3

[Владимир Олохтонов]

N — число элементов в матрице, а K — необходимое число элементов на хвосте отсортированного массива.

Заведем структуру MatrixEntry { value, row, column }.

Совсем тупое решение:
Сформируем массив размера N, обойдём нашу матрицу и запишем каждый её элемент в виде такой структуры в список. Список отсортируем и возьмём K последних элементов.
T = O(NlogN)
M = O(N)

Вариант поумнее:
Заведём MinHeap размера K, обходя матрицу будем вставлять в кучу новые MatrixEntry, поддерживая размер кучи, после завершения обхода в куче будет K максимальных элементов.

T = O(NlogK)
M = O(N)

Быстрый вариант:
www.e-maxx-ru.1gb.ru/algo/kth_order_statistics
Находим (N-K)-ю порядковую статистику на массиве элементов, затем обходим его, сравнивая элементы со статистикой. Если элемент больше найденной статистики, то выписываем его.

T = O(N)
M = O(N)