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

This question already has an answer here:

这个问题已经有了答案:

• Find local minimum in n x n matrix in O(n) time 6 answers
• 在n×n矩阵中求出局部最小值。

Given an N-by-N array a of N² distinct integers, design an O(N) algorithm to find a local minimum: an pair of indices i and j such that:

给定N乘N数组a的N2个不同的整数，设计一个O(N)算法来找到一个局部最小值:一对指数i和j:

• a[i][j] < a[i+1][j]
• [我][j]<(i + 1)[j]
• a[i][j] < a[i-1][j]
• [我][j]<(张)[j]
• a[i][j] < a[i][j+1]
• [我][j]<[我][j + 1)
• a[i][j] < a[i][j-1]
• [我][j]<[我][j - 1]

I found this question in a an online algorithm book, Introduction to Programming in Java, chapter 4.2: Sorting and Searching.

我在一个在线算法书中发现了这个问题，在Java中介绍了编程，第4.2章:排序和搜索。

It is similar to problem 35 (same page):

类似于第35题(同页):

• Given an array of N real numbers, write a static method to find in logarithmic time a local minimum (an index i such that a[i-1] < a[i] < a[i+1]).
• 给定一个N个实数的数组，写一个静态方法，在对数时间内找到一个局部最小值(我这样的索引是一个[i-1] < a[i] < a[i+1])。

It has some sort of binary search based solution which I am not able to find out.

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

3 个解决方案

#1

The same problem is mentioned in web version of book Algorithms by Robert Sedgewick and Kevin Wayne. (See "Creative problems" section, problem 19).

罗伯特·塞奇威克(Robert Sedgewick)和凯文·韦恩(Kevin Wayne)在《图书算法》的网络版中也提到了同样的问题。(参见“创意问题”部分，第19题)。

The hint for the problem given by author in that link is:

作者在该链接中给出的问题的提示是:

Find the minimum in row N/2, check neighbors p and q in column, if p or q is smaller then recur in that half.

在第N/2行找到最小值，在列中检查邻居p和q，如果p或q小于那一半。

A better aprroach would be : Find the minimum in row N/2, check all entries in its column, if we get smaller entry in column, then recur in the row where smaller column entry belongs.

一个更好的方法是:在第N/2行中找到最小值，检查其列中的所有条目，如果我们在列中得到更小的条目，那么在较小的列条目所属的行中再次出现。

eg. For array below, N=5:

如。下面为数组,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

Step 1: The middle row is [4 5 6 -1 77]. ie. row number 3.

第1步:中间一行是[4 5 6 -1 - 77]。ie。行3号。

Step 2: Minimum entry in current row is -1.

步骤2:当前行的最小输入为-1。

Step 3: Column neighbors for min entry (ie. -1) are 5 and -2. -2 being the minimum neighbor. Its in the 4th row.

步骤3:为最小项的列邻居(ie)。-1)是5和-2。-2是最小的邻居。它在第四行。

Continue with steps 2-3 till we get the local min.

继续步骤2-3，直到我们得到局部最小值。

EDIT:

编辑:

For example mentioned in comment from @anuja (the main problem is for n-by-n array. This input is 3-by-4 array but we can work with that) :

例如@anuja的注释(主要问题是n×n数组)。这个输入是3×4的数组，但是我们可以这样做):

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

Step 1: The middle row is [5 1 6 -1]. ie. row number 2.

第1步:中间一行是[5 1 6 -1]。ie。行2号。

Step 2: Minimum entry in current row is -1.

步骤2:当前行的最小输入为-1。

Step 3: Column neighbors for min entry (ie. -1) are 4 and -2. -2 is the minimum column neighbor. Its in the 3rd row.

步骤3:为最小项的列邻居(ie)。-1)是4和-2。-2是最小列邻居。它在第三行。

Iterating to Step 2: -2 is smallest in its row and smallest amongst its column neighbours. So we end with -2 as output for local minimum.

迭代到步骤2:-2在它的行中最小，在它的列邻居中最小。我们以-2作为局部最小值的输出。

#2

Update: This answer is assuming that edges are not local minima, as they are not defined as such by the four comparisons in the original problem statement. In this case this answer is correct (it is not possible). If you redefine the question such that edges can be local minima, than every matrix contains at least one local minima - and hence you can use a a divide-and-conquer approach.

更新:这个答案是假设边缘不是局部最小值，因为它们没有被定义为在原始问题语句中的四个比较。在这种情况下，这个答案是正确的(这是不可能的)。如果你重新定义了这样一个问题，即边可以是局部最小值，而不是每个矩阵都包含至少一个局部最小值，因此你可以使用一个分治法。

If edge cells cannot be local minima:

如果边缘细胞不能是局部最小值:

There is no solution to the question as stated. An N-by-N array takes O(N^2) time just to read the elements. As there could be a single local minimum "hiding" anywhere in the matrix, this is provably necessary to do.

如前所述，没有办法解决这个问题。N×N数组需要O(N ^ 2)时间就阅读的元素。因为在矩阵中可能有一个局部最小的“隐藏”，这是很有必要的。

If you meant to ask for an O(N^2) algorithm, than simply walking each element and comparing it to its 4 neighbours takes O(N^2) time.

如果你想要求一个O(N ^ 2)算法,每个元素不仅仅是步行,比较4邻国需要O(N ^ 2)时间。

Either you have misremembered the interview question (and there was more to it), or this is just a trivial coding exercise.

要么你记错了面试问题(还有更多的问题)，或者这只是一个简单的编码练习。

Proof:

证明:

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

This matrix has exactly one local minima (M[x,y]), and its location is independent of the values in the other cells. Therefore the other cells provide no information about its location, and so it is impossible to have any system to search for it that has better than an expected (N^2/2) cells searched = O(N^2).

这个矩阵只有一个局部最小值(M[x,y])，它的位置与其他单元格中的值无关。因此，其他的细胞没有提供关于其位置的信息，因此不可能有任何系统去寻找比预期的更好的(N 2/2)细胞。

(In other words you may as well be searching a near all zero matrix M[i,j] = 0 except for M[x,y] = -1 for the minima.)

(换句话说，除了M[x,y] = -1的最小值，你还可以搜索几乎所有的零矩阵M[i,j] = 0)。

This proof depends on being able to construct a matrix with no local minima in step 1. If edge cells are possible local minima than every matrix must have one, and this proof no longer holds.

这个证明取决于能否在第1步中构造一个没有局部最小值的矩阵。如果边缘细胞是可能的局部最小值，那么每个矩阵都必须有一个，而这个证明不再成立。

#3

Visit a random cell. If any of its four neigbors have a smaller value: go to that cell. If none of the neigbors are smaller, you are in a local minimum. Will be a bit harder to avoid loops if cells with equal values are possible.

访问一个随机的细胞。如果它的4个neigbors有一个更小的值:去那个单元格。如果没有任何一个neigbors较小，那么您处于本地最小值。如果具有相同值的单元格是可能的，则要避免循环会有点困难。

Update:

更新:

Instead of visiting one neigbor, we could pick the smallest neigbor.

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

The most difficult topology seems to be the case of two "concentric" spirals, one of them functioning as a spiralling dike. That would in the worst case still take about N/2 steps. (with N=number of cells.)

最困难的拓扑结构似乎是两个“同心”螺旋体，其中一个是螺旋状的岩脉。在最坏的情况下仍然需要N/2步。(N =数量的细胞。)