鞍点的位置

Question

鞍点的位置

5

我有以下问题：

假设我们有一个9*8的矩阵。

如果在某个位置，该矩阵中的数值是其所在行最小值，且所在列最大值，则称该矩阵具有“马鞍点”。用符号表示，a[i][j]是一个马鞍点。

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

请帮我找到山峰的计算机位置。

- user466534

1

你目前取得了什么成就？你遇到了哪些问题？ - Petar Minchev

我不同意。鞍点是指在一个维度上的局部最小值恰好是另一个维度上的局部最大值。它不仅仅是一行中的最低值和一列中的最高值。 - Giovanni Tardini

4个回答

3

简而言之：

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

- Nick Johnson

我不太懂Python，但你说你的第二阶段是O(min(M,N))，然而你声称要返回所有的鞍点。在最坏的情况下，每个点都是一个鞍点，所以第二阶段必须是O(MN)。你如何解释这个问题？（顺便加一分） - polygenelubricants

1

你说得很对 - 它最多会在每行（或者如果你反转最后的循环，则为每列）返回一个鞍点。这可能是一个重要问题，也可能不是，这取决于应用程序，因为在普通情况下（一个没有许多重复值的数组中），只会有一个鞍点。 - Nick Johnson

3

朴素的解决方案是：

找到所有行中最小的值
找到所有列中最大的值
查看它们是否在同一位置

- Unreason

0

你已经回答了这个问题：

找到每行中最小元素的位置，找到每列中最大元素的位置，

两个列表中都出现的任何位置都是鞍点

还有改进的空间 - 但基本上就是这样

- kdo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- polygenelubricants · Accepted Answer

给定一个大小为 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) 个鞍点：那就是当数组中的数字都相等时。