rvk*_*rvk 3 algorithm multidimensional-array data-structures
老实说,这是一个任务问题,但我无法找到解决方案.请记住,我不是要求答案,只是一些指导.
问题:设计一个在O(n)时间(线性)运行的算法,该算法可以在2D网格上定位单个可疑房屋(点).如果消耗等于或大于其两个垂直和两个水平邻居的电力消耗是可疑的.注意:只想要一个可疑的房子被退回
解决方案:甚至不确定如何实现这样的解决方案.如果你检查n个房子,你也可以检查周围的四个邻居.4n/n ^ 2,简化为4/n.这意味着随着网格的扩展,它不太可能找到可疑的房子.
我尝试过: - 不同的数据结构(大多数是nlogn) - 折叠网格(再次nlogn)
提前致谢.
编辑:
我的错误,网格是(nxn)使房屋数量n ^ 2,抱歉混乱.
EDIT2:
这确实是个问题,也许我读错了？
警方正在寻找电力消耗特别大的房屋.为了简化问题,想象一下他们正在调查在n×n网格上布置的房屋.电网上的每个房屋都有一些耗电量e(i,j).如果房屋的电力消耗等于或大于其垂直和水平邻居的每一个,警察会认为该房屋是可疑的.设计一个在O(n)时间内运行并返回可疑房屋位置的算法.
你基本上是在寻找一个用电量最大的房子.您可以通过从任意房屋开始找到其中一个,如果电力使用较高,则可以踩到相邻的房屋(重复直到没有相邻房屋更高).
这将在nxn网格上花费O(n)时间.
编辑:评论者是对的,在最坏的情况下这可能需要O(n ^ 2)时间.