我知道以前有人问过这个问题,但我无法从答案中得出任何结论,所以我希望有人能够以一种非常简单的方式向我解释这个问题....
问题:
一个人站在一堵无限长的墙前。墙的另一边是他正试图前往的城镇。墙上的某个地方有一扇门,那个人可以向左或向右走找到它。
我需要编写一个具有线性运行时间的算法,但我无法解决这个问题......非常感谢任何帮助!
最佳答案
他必须两面都试。然而,如果他只是在每个方向上不断地增加新的长度,这将成为一个“画家施勒米尔”的问题。他需要以指数方式增加他在每个方向上行走的新长度,以便搜索的摊销时间变为线性。您将必须计算出细节以及它们如何转化为复杂性公式。
关于Java:如何在一维图中找到洞?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5883157/