5

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

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

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

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

int main()
{
    int n=0, m=0;
    cin >> n >> m;
    vector<vector<int>> v(n, vector<int> (m)); //Матрица NxM
    vector <int> s(n);
    for(int i=0; i<n; i++)
    {
        int min=0;
        for(int j=0; j<m; j++)
        {
            cin >> v[i][j];
            if(j==0||v[i][j]<min)
                min = v[i][j]; //считываем минимальный элемент каждый из строк
        }
        s[i] = min;
    }
    int sed=0;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(v[i][j] ==s[i]) //бегаем по элементам и когда есть совпадение минимального элемента
                for(int z=0; z<n; z++)//если есть совпадение заходим в цикл
                {
                    if(v[z][j] > v[i][j]) break;//проверяем действительно ли он в столбце максимальный
                    else if(z==(n-1)) sed++; 
                }
        }
    }
    cout << sed;
    return 0;
}
1
  • А вы пробовали кроме минимума по строке, искать максимум по столбцу, после чего увеличивать ответ, если он равен и максимальному в столбце и минимальному в строке. Это уменьшит сложность с O(N^2 M) до O(NM)
    – pavel
    19 янв 2016 в 7:48

2 ответа 2

6

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

  1. Вычислить массив Col[i] индексов (столбцов) наименьшего элемента в i-й строке.
  2. Вычислить массив Str[j] индексов (строк) наибольшего элемента в j-м столбце.
  3. В цикле по i проверять условие Str[Col[i]] == i.
2
  • в таком виде не сработает если минимальные и максимальные элементы будут повторяться в пределах столбца или строки. Определение этого не запрещает "если все элементы в соответствующей строке не меньше его, и при этом все элементы в соответствующем столбце не больше его"
    – rdorn
    21 янв 2016 в 23:03
  • @rdorn Термины "наибольший" и "наименьший" - в какой-то мере подчёркивают единственность элемента. Но раз мы с Вами видим это по-разному, то: 1) постановка задачи нуждается в уточнении и 2) если наибольших и наименьших элементов может быть несколько, то запоминать и перебирать придётся их все 22 янв 2016 в 1:59
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 забираем количество найденных седловых элементов

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.