Как я могу находить минимальную стоимость массива map в c ++?

Я пробую находить минимальную стоимость массива используя методологию "дели и ты победишь".

Для этого я думал о том, чтобы упорядочить массив линию из-за линии, чтобы потом находить Вашу минимальную стоимость, но у меня есть проблема:

Мой массив определен как map<int, map<int, int> > и, попробовав применять функцию sort, () STL, он дает мне ошибку.

Мой код этот:

for(int i = start; i < end; i++){
    sort(matrix[i].begin(), matrix[i].end());
}

Я хочу распределить эту линию в вектор, чтобы мочь выполнять функцию, но не, как делание этого.

Также было бы интересно в случае когда не мочь бы заставлять это преобразование находить другой способ получать этот минимум.

Существует какой-то работоспособный способ находить минимальную стоимость массива с этой методологией?

2
задан 29.12.2016, 08:49
0 ответов

В конце концов, сменил std:: map на std:: вектор определенного размера, жертвуя гибкость и место из-за удобства алгоритма.

Чтобы получать минимум, приложение std:: sort () линия из-за линии, и потом я пробежал первую колонну сравнивая до тех пор, пока несовершеннолетний не получил.

И, чтобы знать, которому положения (x, y) соответствовал этот несовершеннолетний, произведите копию первоначального matrix и я пробежал линию, соответствующую минимуму, до того, чтобы находить данную стоимость.

Таким образом, она x - число линии, и она и это число колонны

0
ответ дан 03.12.2019, 17:56

Ввиду того, что карты упорядочивают из-за ключа и не из-за стоимости, и твои ключи - индексы массива, у тебя не остается другая, который реализовывать линейные поиски. Упорядочивать ты не можешь, потому что maps они не могут быть реорганизованными, ввиду того, что ты ломаешь связь команды, что сам map попробуй защищать, отсюда следует, что ты ошибки компиляции. Кроме того, в случае, если ты мог (используя другую структуру данных), приказывать только, чтобы искать минимум, неэффективно также. Цена упорядочивания - всегда больше, чтобы искать один одного. Ты нуждаешься в том, чтобы упорядочить, когда ты будешь нуждаться в стоимости, упорядоченной для более чем одной вещи. Так что:

#include <limits>

int min = std::numeric_limits<int>::max(); // Infinito
int i_min, j_min; // Coordenadas del mínimo

for (int i = start; i < end; ++i)
    for (int j = start_dim2; j < end_dim2; ++j)
       if (matrix[i][j] < min) {
            min = matrix[i][j];
            i_min = i;
            j_min = j;
       }

Это работоспособнее, что использовать std::sort или любой другой механизм, который приходит в голову тебе. Могут быть другие более работоспособные решения, но все зависит от, почему ты представляешь массивы с maps, или зачем у тебя хотели бы быть аккуратные элементы.

1
ответ дан 03.12.2019, 17:56

Ты должен копировать все элементы твоего массива в договоренность unidimensional, следующей формы:

vector<int> arregloTotal;
for(int i=0;i<matriz.length;i++){
 for(int k=0;k<matriz[0].length;k++){
      arregloTotal.push_back(matriz[i][j]);
 }
}

arregloTotal у него есть все элементы твоего массива

0
ответ дан 03.12.2019, 17:56
  • 1
    и ¿ какая-то более работоспособная форма не существует? Хусто querí чтобы это предотвращать –  28.12.2016, 23:16
  • 2
    @AlmuHs этого нет –  28.12.2016, 23:23