最近我参加了一个编码竞赛,无法弄清楚这个问题.问题陈述如下
你有一个
10^9 * 10^9白色格子网格,10^5黑色.对于j来自0to的每个整数9,输出包含正好j黑色单元格的3x3子矩形的数量.时间限制为3秒,内存限制为256mb.
我有一个模糊的想法,例如:迭代黑色单元格并检查以黑色单元为中心的5x5矩形中的单元格,然后计算3x3矩形(我相信这将是一个O(n)解决方案,其中n是黑色单元格的数量,但我不知道如何实现这个或如何处理重复计算.
该网站有一个针对此问题的编辑,但它是日文和谷歌翻译是没有用的.
我的算法如下：
有 2 个有序集，1用于点，1 个有序集用于每个子矩形的左上角坐标3x3。这是为了有效搜索重复项和黑色单元格
对于每个黑色单元格，处理3x3它所在的 9 个矩形
对于每个3x3矩形，检查左上角坐标是否已在集合中
2a. 如果是，则忽略矩形
2b. 如果不是，则计算矩形中黑色单元格的数量（通过检查每个单元格中是否存在黑色单元格）
将新的左上角坐标插入到集合中并添加1到适当的计数器。
3x3要计算没有任何黑色单元格的矩形的数量，您可以采用(H-2)*(W-2) - number of rectangles with at least 1 black cell
该算法应该采取~O(Nlog(N))步骤。步骤 1 需要O(N)时间，步骤 2 需要时间O(9*9*logN) = O(logN)。第 3 步需要O(logN)时间。