Расположение седловой точки

Question

У меня следующая проблема

Предположим, что у нас есть матрица 9 * 8

Говорят, что матрица имеет "седловую точку", если в какой-то позиции это наименьшее значение вего строка и наибольшее значение в его столбце.В символах a [i] [j] является седловой точкой, если

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

Пожалуйста, помогите мне найти компьютерную точку седловой точки.

Answer 1

Учитывая MxN матрица, это O(MN), что является оптимальным.

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)

---

Почему это оптимально?

Поскольку существуют значения MxN , и на каждое из них необходимо обратить внимание, поэтому для того, чтобы ваш ответ был определенным (т.е. не вероятностным), нижняя граница равна O(MN).

Можно ли это оптимизировать дальше?

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

Обратите внимание, что в худшем случае есть O(MN) седловые точки: тогда все числа в массиве равны.

Answer 2

В двух словах:

1. Итерация по каждой строке, поиск номера столбца наименьшего значения в этой строке.
2. Итерация по каждому столбцу, поиск номера строкинаибольшее значение в этом столбце.
3. Выполните итерацию по строкам-минутам или столбцам-максимумам, проверяя, является ли соответствующая ячейка также максимальной в другом массиве.

Вот реализация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 3

Наивное решение заключается в:

• найти наименьшие значения из всех строк
• найти самые большие значения столбцов
• посмотрим, находятся ли какие-либо из них в одной позиции

Answer 4

вы сами ответили на вопрос:

найдите позицию минимального элемента в каждой строке, найдите позицию максимального элемента в каждом столбце,

любую позицию, которая встречается в обоих спискахэто седловая точка

есть возможности для улучшения - но в принципе, это все