在二维数组中找到局部最小值
给定N个N 个不同整数的N-by-N阵列,设计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]
我在一本在线算法书" Java编程入门",第4.2章:排序和搜索中找到了这个问题.
它类似于问题35(同一页面):
- 给定一个N个实数的数组,写一个静态方法,在对数时间内找到一个局部最小值(索引i就是这样
a[i-1] < a[i] < a[i+1]).
它有一些基于二进制搜索的解决方案,我无法找到.
Robert Sedgewick和Kevin Wayne在网络版的算法中提到了同样的问题.(参见"创造性问题"部分,问题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].即.第3行.
第2步:当前行的最小条目是-1.
步骤3:min entry(即.-1)的列邻居是5和-2.-2是最小的邻居.它在第4排.
继续步骤2-3,直到我们获得当地最低分.
编辑:
例如@anuja的评论中提到的 (主要问题是n-by-n数组.这个输入是3乘4的数组,但我们可以使用它):
1 2 3 4
5 1 6 -1
7 3 4 -2
第1步:中间一行是[5 1 6 -1].即.第2行.
第2步:当前行的最小条目是-1.
步骤3:min entry(即.-1)的列邻居是4和-2.
-2是最小列邻居.它在第3排.
迭代到步骤2:-2在其行中最小,在其列邻居中最小.所以我们以-2作为局部最小值的输出结束.
- 在最坏的情况下,这是n ^ 2.考虑一个数组,该数组包含一组来回的数字,每行由一个较大数字的墙隔开.你将循环n*(n/2)/ 2次跟随链到它的结束.我想如果我们在包含低值的列的重复1,2的#2之后添加一个步骤,然后继续进行2,3循环,那就是O(n). (3认同)
- 这个算法有点怪,但它不是O(n).找到连续的最小值是O(n).我们必须找到最小行的次数可以取决于n(对于某些矩阵模式).可以构造一个矩阵,强制算法访问所有行和列.考虑带有行的矩阵:"8 3 4 8","8 8 8 7","8 8 5 6"和"1 2 8 8".您的算法将访问所有行和所有列,使其成为"O(n ^ 2)"算法.(因此,对于这个输入矩阵,只需循环遍历所有元素并在整个矩阵中找到最小元素将更有效) (3认同)
更新:这个答案假设边缘不是局部最小值,因为它们没有通过原始问题陈述中的四个比较来定义.在这种情况下,这个答案是正确的(这是不可能的).如果你重新定义边缘可以是局部最小值的问题,那么每个矩阵至少包含一个局部最小值 - 因此你可以使用分而治之的方法.
如果边缘单元格不能是局部最小值:
如上所述,问题没有解决方案.N-by-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中构造没有局部最小值的矩阵. 如果边缘单元是可能的,则局部最小值比每个矩阵必须具有一个,并且该证明不再成立.