4

我试图为以下问题发明一种有效的算法，但我认为我失败了。我得到了一个n * n的棋盘，里面有不同的数字和一个整数k (k <= n)。我必须在棋盘中找到一个正方形k * k，其中不同数字的数量最大。对于那些例子：

n=4 k=3
10 9 8 1
7 6 5 7
5 3 0 2
3 4 1 3

n=4 k=2
1 2 1 2
2 1 2 1
1 2 1 2
2 1 3 4

答案如下：

9 8 1
6 5 7
3 0 2

1 2
3 4

我对这个问题的解决方案（在 C++ 中）是基于选择左上角的第一个正方形 k*k，创建一个将数字（键）与其出现频率（值）联系起来的映射。然后，我通过删除地图中正方形的第一列并添加下一列，将正方形进一步移动一列。当我到达右侧时，我向下移动一排，然后向左移动到边界。然后向下一步，直接到边界。依此类推，直到我到达终点。答案基于特定时刻地图的最大尺寸。我认为这个解决方案的发明很糟糕（但可能仍然比蛮力更好），我很感激任何建议。这个问题可以以某种方式简化为修改后的最大矩形问题吗？( http://www.drdobbs.com/database/184410529 )



根据 Daniele 的建议编辑（附加细节）

一开始我的算法分析了第一个 k*k 平方，即： 10 9 8 | 7 6 5 | 5 3 0. 在分析每个元素时，它会将适当的数据写入地图。所以起初我有一对（10 -> 1）（数字10出现一次），然后我添加（9 -> 1），（8 -> 1），（7 -> 1），（6 -> 1）， （5 -> 1）。然后我遇到下一个 5，所以我将它的出现更改为两个 (5 -> 2)。最后我添加 (3 -> 1), (0 -> 1)。实际上我的地图包含 8 个元素（因为如上所述，5 个出现了两次）。我记得这个正方形坐标和地图的大小。我将我的 k*k 方格向右移动一列。因此，我减少了地图第一列中元素的出现。所以我删除对 (10 -> 1) 和 (7 -> 1) 并将 (5 -> 2) 更改为 (5 -> 1)。我添加了最后一列：(1 -> 1)、(7 -> 1) 和 (2 -> 1)（因为所有数字都是新的）。现在我注意到地图的大小比以前大（ 9 > 8 ），所以我将当前坐标保存在旧坐标之上。实际上我在这里结束我的算法（我的附加条件： if(map.size() == k*k) end; ）但否则我会“去”比左边低一排直到边界，这样我会已完成对所有可能的 k*k 方格的分析。

实际上，我正在寻找一种更好的时间消耗解决方案，因为我的解决方案被测试系统拒绝（我超过了时间限制）。我认为它比蛮力更好，因为我不会一一分析每个方块，但我可能错了。无论如何，它仍然不够好。

我可以附上 C++ 代码，以防你更容易，但我怀疑它会有所帮助。我只是在寻找算法建议。

4

1 回答 1

1

您的算法听起来不错，具有O(n * n * k * log k)时间复杂度和O(k * k)内存。如果您知道示例中的值是小整数，则可以log k通过将映射替换为数组来摆脱 。否则，实现算法的代码可能效率低下。尝试根据您的变化对代码进行计时n，并k查看时间是否按预期增长。

作为另一个可能的方向，您可以尝试动态编程风格的解决方案。定义函数f(x, y, a, b)以计算锚定于 的axb矩形中的唯一值集（可能是位图） (x, y)。那么问题是找到 的最大值|f(x, y, k, k)|。被计算为 4 个或更多具有大约x维f(x, y, a, b)的较小矩形集的并集。如果缓存了较小的矩形集，则不必继续重新计算它们。缓存将占用大量内存，但您可以通过安排分解以使用 2 大小的幂来限制它。例如，a/2b/2

  f(x, y, 21, 21) = f(x, y, 16, 16)
                    union f(x + 16, y, 4, 16)
                    union f(x + 20, y, 1, 16)
                    union f(x, y + 16, 16, 4)
                    union f(x, y + 20, 16, 1)
                    union f(x + 16, y + 16, 4, 4)
                    union f(x + 20, y + 16, 1, 4)
                    union f(x + 16, y + 20, 4, 1)
                    union f(x + 20, y + 20, 1, 1)

我认为这种方法更像 O(n * n * log k * log k) ，因此只会为较大的值（k例如大于 1000）带来回报。

于 2012-06-16T03:36:34.760 回答