Saddle point location

Question

I have the following problem:

Suppose we have a 9 * 8 matrix

It is said that a matrix has a “saddle point” if at some position it is the smallest value in its row and the largest value in its column. In the characters a [i] [j] is a saddle point if

 a[i][j]=min a[i][k]  ==max a[k][k]
             1<=k<=8      1<=k<=9

Please help me find the location of the computer at the saddle point.

Answer 1

Given the MxN matrix, this O(MN)is what is optimal.

INIT rowMin = [ +Infinify ] xM
INIT colMax = [ -Infinity ] xN

FOR r = 1..M
  FOR c = 1..N
    rowMin[r] = MIN(rowMin[r], mat[r][c])
    colMax[c] = MAX(colMax[c], mat[r][c])

FOR r = 1..M
  FOR c = 1..N
    IF mat[r][c] == rowMin[r] == colMax[c]
       DECLARE saddlePoint(r, c)

---

Why is this optimal?

Because there are MxN values, and each of them must be viewed, therefore, for your answer, to be sure (that is, not probabilistic), the lower level O(MN).

?

. O(MN), , / , . O(M) (.. / min/max).

, O(MN) : .

Answer 2

:

• , - .

Answer 3

:

• , .
• , .
• Iterate through min-rows or maxes-columns, checking if the corresponding cell also matches max in another array.

Here's the implementation in Python:

def find_saddle_points(a):
  """Finds saddle points in a, a 2 dimensional array.

  Args:
    a: A 2 dimensional array in row-major (y, x) order.
  Returns:
    A list of (x, y) location of the saddle points.
  """
  # Holds a (value, column) tuple of the min value and its column for each row.
  row_mins = [min((a[row][col], col) for col in range(len(a[row]))) for row in range(len(a))]
  # Holds a (value, row) tuple of the max value and its row for each column.
  col_maxes = [max((a[row][col], row) for row in range(len(a))) for col in range(len(a[0]))]

  ret = []
  for row, (row_min, col) in enumerate(row_mins):
    if col_maxes[col][1] == row:
      ret.append((row, col))
  return ret

Answer 4

you yourself answered the question:

find the position of the minimum element in each row, find the position of the maximum element in each column,

any position that appears in both lists is a saddle point

there is room for improvement - but in principle, that he