Алгоритм поиска седловых точек в двумерном массиве

Question

Я ищу алгоритм для нахождения положений всех седловых точек в матрице NxN.

Поиск по другим ответам на StackOverflow, а также на других сайтах в целом, я нашел решения, касающиеся седловых точек, которые работают в одном направлении. То есть, я хочу найти седловую точку, которая может быть максимальной в ее строке и минимуме в ее столбце, или минимум в ее строке и максимуме в ее столбце.

Например, учитывая:

array = { 
{ 10, 15, 20, 15, 10 } 
{ 5, 10, 15, 10, 5 } 
{ 0, 5, 10, 5, 0 } 
{ 5, 10, 15, 10, 5 } 
{ 10, 15, 20, 15, 10 } }, 

седловые точки являются 10-х в углах и 10 в середине.

Я могу найти их наивно довольно легко, но я хотел чего-то более эффективного. Мне сказали, что это можно сделать в O (n^2).

Я подумал, что, возможно, я мог бы исправить координату x и итерации через y-координату, чтобы найти все максимумы и минимумы, а затем отменить процесс, зафиксировав y-координату и итерацию через координату x, но я могу " t достаточно визуализировать его достаточно хорошо, чтобы реализовать эту идею.

Любая помощь была бы принята с благодарностью.

Answer 1

Обратите внимание, что в наивной реализации O (n) вы пересчитываете максимальное значение и минимальное значение для каждого элемента строки/столбца, который вы проходите.

Чтобы устранить эту неэффективность, идея состоит в том, чтобы прокручивать каждую строку и столбец и отмечать все позиции с максимальным и минимальным значением в отдельном массиве N x N. Каждый элемент этого отдельного массива содержит 2 фрагмента логической информации: isMax и isMin (которые могут быть закодированы как бит, если вы хотите). Если все элементы в строке/столбце одинаковы (т. Е. Максимальное значение = минимальное значение), вы можете не захотеть отмечать какой-либо элемент.

Для каждой строки/столбца это можно сделать в O (n) времени. Используйте массив n-элементов для записи индексов с текущим максимальным (минимальным) значением и очистите массив, если есть большее (меньшее) значение, чем текущий максимум (минимум). После того, как вы закончите цикл, используйте информацию из массива максимальных (минимальных) индексов, чтобы отметить соответствующее поле isMax (isMin) в массиве N x N.

Поскольку существует п строк и п столбцов, сложность этого шага О (п)

Тогда остальное в цикле через N массив N х, которые вы отметили для поиска любой положение с isMax и isMin комплект.

Answer 2

O (N^2)

#include <stdio.h> 

#define N 8 
#define M 10 

int arr[N][M] = 
{ {1,2,0,3,9,4,5,3,6,7}, 
    {2,4,3,5,9,0,2,3,4,1}, 
    {5,3,4,7,6,1,9,0,4,2}, 
    {6,9,7,8,6,7,7,4,5,6}, 
    {8,3,1,9,2,0,6,2,8,2}, 
    {2,7,3,0,3,6,3,1,5,3}, 
    {8,2,5,9,7,7,8,3,7,3}, 
    {1,7,4,8,5,8,5,0,0,6} }; 

int FindSaddlePoints(int arr[N][M]) 
{ 
    int l_result = 0; 

    int l_row[M], l_column[N], i, j, index; 

    //find the min 
    for (i = 0; i < N; i++) 
    { 
     index = 0; 
     for (j = 1; j < M; j++) 
     { 
      if (arr[i][j] < arr[i][index]) 
      { 
       index = j; 
      } 
     } 
     l_column[i] = index; 
    } 

    for (j = 0; j < M; j++) 
    { 
     index = 0; 

     //find the max 
     for (i = 1; i < N; i++) 
     { 
      if (arr[i][j] > arr[index][j]) 
      { 
       index = i; 
      } 
     } 
     l_row[j] = index; 
    } 

    for (i = 0; i < N; i++) 
    { 
     for (j = 0; j < M; j++) 
     { 
      if (l_row[j] == i && l_column[i] == j && i != N && j != M) 
      { 
       //printf("found in row = %d column = %d", i, j); 
       l_result++; 
      } 
     } 
    } 

    return l_result; 
} 
void main() 
{ 
    int number = FindSaddlePoints(arr); 

    printf("%d", number); 
}