在二维数组中找到局部最小值[重复]

Question

给定一个由 N² 个不同整数组成的 N×N 数组 a，设计一个 O(N) 算法来查找局部最小值：一对索引 i 和 j，使得：

• a[i][j] < a[i+1][j]

• a[i][j] < a[i-1][j]

• a[i][j] < a[i][j+1]

• a[i][j] < a[i][j-1]

我在一本在线算法书籍中找到了这个问题，Introduction toProgramming in Java, Chapter 4.2: Sorting and Searching。

与问题35类似（同一页）：

• 给定一个由 N 个实数组成的数组，编写一个静态方法来在对数时间内找到局部最小值（索引 i 使得

  a[i-1] < a[i] < a[i+1]

  ）。

它有某种基于二分搜索的解决方案，我无法找到。

Answer 1

Robert Sedgewick 和 Kevin Wayne 所著的Algorithms 网络版书中提到了同样的问题。 （参见“创意问题”部分，问题 19）.

作者在那个链接中给出的问题提示是：

找到第 N/2 行中的最小值，检查列中的邻居 p 和 q，如果 p 或 q 较小，则在该一半中重复。

更好的方法是： 找到第 N/2 行中的最小值，检查其列中的所有条目，如果我们在列中得到较小的条目，则在较小列条目所属的行中重复。

例如。 对于下面的数组，N=5:

1  12  3   1  -23  
7   9  8   5   6
4   5  6  -1  77
7   0  35 -2  -4
6  83  1   7  -6

第1步：中间一行是[

4   5  6  -1  77

]。 IE。行号 3.

第 2 步：当前行的最小条目为

-1

。

第 3 步：最小条目（即

-1

）的列邻居是

5

和

-2

。

-2

是最小邻居。它在第四排。

继续执行步骤 2-3，直到获得 本地最小值。

例如@anuja 的评论中提到的 （主要问题是 n×n 数组。这个输入是 3×4 数组，但我们可以使用它） :

1 2 3  4 
5 1 6 -1
7 3 4 -2

第1步：中间一行是

[5 1 6 -1]

。 IE。行号 2.

第 2 步：当前行的最小条目为

-1

。

第 3 步：最小条目（即

-1

）的列邻居是

4

和

-2

。

-2

是最小列邻居。它在第三排。

迭代第 2 步：-2 在其行中是最小的，在其相邻列中也是最小的。所以我们以 -2 作为局部最小值的输出结束。

Answer 2

这个答案假设边缘不是局部最小值，因为它们不是由原始问题陈述中的四个比较定义的。 在这种情况下，这个答案是正确的（这是不可能的）。 如果您重新定义问题，使得边缘可以是局部最小值，则每个矩阵都至少包含一个局部最小值 - 因此您可以使用分而治之的方法。

如果边缘单元不能是局部最小值：

所提出的问题没有解决方案。 N×N 数组仅读取元素就需要 O(N^2) 时间。 由于矩阵中的任何位置都可能存在单个局部最小值“隐藏”，因此这被证明是必要的。

如果您想要一个 O(N^2) 算法，那么简单地遍历每个元素并将其与其 4 个邻居进行比较需要 O(N^2) 时间。

要么你记错了面试问题（而且还有更多问题），要么这只是一个微不足道的编码练习。

证明：

1. Construct a NxN matrix such that each cell has the value M[i,j] = N*i + j.
2. Select a random x,y (1 < x < N and 1 < y < N) and assign M[x,y] = -1

该矩阵恰好有一个局部最小值 (M[x,y])，并且其位置与其他单元格中的值“独立”。 因此，其他单元格不提供有关其位置的任何信息，因此不可能有任何系统来搜索它，其搜索结果优于预期的 (N^2/2) 个单元格 = O(N^2)。 （换句话说，除了最小值 M[x,y] = -1 之外，您还可以搜索几乎全零的矩阵 M[i,j] = 0。）

该证明取决于能够在步骤 1 中构造一个没有局部最小值的矩阵。

如果边缘单元可能是局部最小值，则每个矩阵都必须有一个，

并且该证明不再成立。

Answer 3

我们可以选择最小的邻居，而不是访问一个邻居。

最困难的拓扑结构似乎是两个“同心”螺旋的情况，其中一个充当螺旋堤坝。在最坏的情况下，仍然需要大约 N/2 步。 （N=细胞数量。）