4

我很快就要参加我的数据结构课程的考试了。为了做好准备，我正在查看我在网上找到的一些基于算法的问题，并遇到了一个我似乎无法解决的问题。

你走进一个房间，看到一排 n 张牌。每个都写有一个数字 xi，其中 i 的范围从 1 到 n。然而，最初所有的牌都是面朝下的。你的目标是找到一个局部最小值：即一张卡片 i 的数量小于或等于其邻居的数量，xi-1 >= xi <= xi+1。第一张和最后一张牌也可以是局部最小值，它们只有一个邻居可以比较。显然可以有许多局部最小值，但您只负责找到其中一个。

我能想出的唯一解决方案基本上是将它们全部翻转并找到任何局部最小值。然而，挑战在于仅通过翻转 O(logn) 卡来做到这一点。

本质上，如果你看到一张卡片“7”，如果左边的卡片是“10”而右边的卡片是“9”，那么它就是局部最小值。这如何在登录时间内轻松完成？

任何帮助表示赞赏，谢谢。

4

1 回答 1

4

二进制搜索是要走的路。这是您如何做到这一点的粗略草图：

  1. 查看第一个和最后一个元素。如果其中一个是一分钟，则返回它。
  2. 看中间元素。如果是一分钟就退货。否则它的左邻居或右邻居必须小于它。递归那一半。

所以这个想法是，如果我们知道中心元素的左邻居比它小，那么左半部分必须在某个地方有一个局部最小值，这样我们就可以安全地在那里递归。右半部分也是如此。

换句话说，一半数据没有本地最小值的唯一方法是它要么是单调的，要么是上下波动，这两种情况都不会发生，因为我们知道端点值。

此外，运行时间显然是 log(n)，因为每个步骤都需要恒定的时间，而且我们必须执行 log(n) 步骤，因为我们每次都将数据减半。

于 2013-05-07T01:00:14.287 回答