Задача седловые элементы матрицы

#cpp #алгоритм

Условие задачи:


  Дана матрица aij размером n × m, состоящая из целых чисел. Требуется
  определить количество седловых элементов матрицы. Элемент матрицы
  aij называется седловым, если он является наименьшим в i-й строке и
  наибольшим в j-м столбце. Иными словами, элемент матрицы является
  седловым, если все элементы в соответствующей строке не меньше его, и
  при этом все элементы в соответствующем столбце не больше его


Моя ошибка заключается в превышении максимального времени работы (ограничение задачи
2 секунды)

вот само решение на C++

int main()
{
    int n=0, m=0;
    cin >> n >> m;
    vector> v(n, vector (m)); //Матрица NxM
    vector  s(n);
    for(int i=0; i> v[i][j];
            if(j==0||v[i][j] v[i][j]) break;//проверяем действительно ли он в
столбце максимальный
                    else if(z==(n-1)) sed++; 
                }
        }
    }
    cout << sed;
    return 0;
}

    

Ответы

Ответ 1

Проще поступить так:


Вычислить массив Col[i] индексов (столбцов) наименьшего элемента в i-й строке.
Вычислить массив Str[j] индексов (строк) наибольшего элемента в j-м столбце.
В цикле по i проверять условие Str[Col[i]] == i.


Ответ 2

Вариант решения с учетом возможных повторений минимумов и максимумов.
Не претендует на идеальный, памяти многовато ест. скорее всего можно оптимизировать.

Временная сложность O(MxN), Использование дополнительной памяти O(MxN)

Код на C#, но кроме двумерных массивов в данном фрагменте все идентично C++, адаптация
не должна стать проблемой.

int m;//Количество столбцов
int n;//Количество строк
//читаем M и N
int[,] source = new int[m, n];//исходная матрица
int[,] finder = new int[m, n];//матрица поиска
//заполняем исходную матрицу любым способом
//заполняем матрицу поиска нулями
for (int j = 0; j < n; j++){
    //ищем минимум в строке
    int minInd = 0;
    for (int i = 1; i < m; i++)
        if (source[minInd,j]>source[i,j])
            minInd = i;
    //Отмечаем на матрице поиска все минимумы прибавляя 1
    for (int i = 0; i < m; i++)
        if (source[minInd, j] == source[i, j])
            finder[i, j]++;
}
//Повторяем все то же для максимумов столбцов
for (int i = 0; i < m; i++){
    int maxInd = 0;
    for (int j = 1; j < n; j++)
        if (source[i, maxInd] < source[i, j])
            maxInd = j;
    for (int j = 0; j < n; j++)
        if (source[i, maxInd] == source[i, j])
            finder[i, j]++;
}
int result = 0;
for (int j = 0; j < n; j++)
    for (int i = 1; i < m; i++)
        if (finder[i, j] == 2)//если минимум строки и максимум столбца 
            result++;         //совпали, ячейка матрицы поиска будет равна 2

//из result забираем количество найденных седловых элементов