通过查看它可能出错的方式,我们可以像贾里德的答案那样改编单词。
答案中的一个主意是“滚下坡路”,这是一个好主意。这只是意味着,如果您在元素上,请检查它是否是局部最小值。如果是这样,那么您就完成了;否则,请移至与其最近的邻居中的最小邻居。最终,这必须终止,因为每一步都是针对较小的元素,并且不能永远在有限的数组中进行。
这种方法的问题在于,“滚动”会在各处蔓延:
20 100 12 11 10 100 219 100 13 100 9 100 318 100 14 100 8 100 417 16 15 100 7 6 5
如果从左上方开始并“下坡”,您将访问数组中大约一半的元素。太多了,因此我们必须对其加以限制。
首先检查中间列和中间行。在所有这些元素中找到最小的元素,然后从那里开始。
从那里“下坡”滚动一步,进入四个象限之一。您将输入一个象限,因为中间列和/或行中的相邻元素较大,因此,两个相邻象限中只有一个是“下坡”的。
现在考虑如果您从那里“下坡”会发生什么。显然,您最终将达到本地最低要求。(我们实际上不会这样做,因为它会花费太长时间。) 但是
,在滚动过程中,您永远不会离开该象限…因为这样做,您将不得不越过中间列或中间行,这些元素都不比您开始的地方小。因此,该象限在某处包含局部最小值。
因此,在线性时间内,我们确定了必须包含局部最小值的象限,并且将n切成两半。现在只需递归即可。
该算法需要2n + 2n / 2 + 2n / 4 + …的时间,等于4n,即O(n),所以我们完成了。
有趣的是,除了关键部分外,我们根本没有使用“向下滚动”:证明算法有效。
[更新]
正如Incassator指出的那样,这个答案并不完全正确,因为在您“递归”之后,您可能会再次退出象限…
最简单的解决方法是在“下坡”之前找到中间行,中间列 和边界 中的最小元素。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)