Как найти седловые точки в двумерном массиве?

Question

Я пытаюсь написать псевдокод, чтобы найти все точки седла в 2D-массиве. Седловые точки - это пятна, где значение - это минимальное значение в его строке, но максимальное значение в его столбце или максимальное значение в его строке и минимальное значение в его столбце.

У меня возникли проблемы с тем, как хранить эти значения, особенно если в одной строке или столбце есть две точки седла. Я также не уверен, что если я даже приблизился к этому правильно, возможно, это можно сделать более эффективным способом?

Массив задается A [x] [y], где x - строка, а y - столбец.

До сих пор мой (очень простой) псевдокод

for r=0 to y-1 // iterates through every row 
    for c=0 to x-1 //iterates through every element in row r 
     min=min(A[c][r]) //finds the minimum value in row r 
    for p=0 to y-1   //iterates through every element in col c 
     max=max(A[c][p]) //finds max in col c 
    if min==max    
     saddle point=A[c][p] 

Answer 1

Вы, кажется, есть две основные проблемы с псевдокоде.

1) Вы обменяли на баран и colums

2) Переходя к элементу массива (он же значение) в мин/макса не имеет особый смысла. Вероятно, вы должны передать номер строки и вернуть функцию номер столбца.

Простым способом является поиск индекса столбца, содержащего минимальное значение в строке r. Затем найдите индекс строки, содержащей максимальное значение в этом столбце. Если индекс двух строк один и тот же, у вас есть седло.

что-то вроде:

for r=0 to x-1 // iterates through every row 

    // Check min-max combination 

    c = min_in_row(r)  //find index of the column holding the minimum value in row r 

    r2 = max_in_column(c) //find index of the row holding the maximum value in column c 

    if (r == r2) 
    { 
     // Saddle point found 
     printf("r=%d c=%d value %d is a saddle point\n", r, c, A[r][c]); 
    } 

    // Repeat the same for the max-min combination 

Answer 2

Любая точка седло может храниться с (строка, столбец). В C:

struct Saddle { int row, col; }; 

Если максимальное число ожидаемых точек перевала известен результат массив может быть использован:

/* max. number of saddle points */ 
#define MAX_FOUND 16 
/* row/col. of found saddle points */ 
struct Saddle found[MAX_FOUND]; 
/* number of found saddle points */ 
int nFound = 0; 

Чтобы сохранить новый результат:

found[nFound].row = r; 
found[nFound].col = c; 
++nFound; 

Если число ожидаемых седловых точек неизвестен. Возможны два варианта:

1. размер массива x * y (Hmm.)

2. выделить хранилище для массива с помощью malloc.

Для 2-го варианта malloc/realloc могут быть использованы. Часто используется трюк: если в памяти заканчивается память, realloc используется для выделения нового пространства для нескольких дополнительных элементов. Таким образом, количество перераспределений уменьшается, потому что realloc считается «дорогой» операцией. В этом случае используются две переменные count: один для размера выделенного массива, другой для числа фактически используемых элементов. Конечно, второе должно всегда быть меньше или равно первому.