@Vovasab

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

Вывести 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);
    }
  • Вопрос задан
  • 724 просмотра
Решения вопроса 3
Zoominger
@Zoominger
System Integrator
Идея: найти наибольшее число каждой строки, загнать их в отдельный массив, отсортировать по возрастанию и взять пять крайних чисел.
Ответ написан
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Берёте три массива по пять элементов, в первом будет сами числа, во втором и третьем - индексы. Инициализируете массивы индексов значениями -1.
Обходите всю матрицу и для каждого элемента матрицы проверяете все элементы массива. Если в массиве есть элемент с индексами -1 или значение в массиве меньше, чем элемент матрицы, то записываете в массив значение из матрицы с его индексами.
Ответ написан
Комментировать
sgjurano
@sgjurano
Разработчик
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)
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы