algorithm - 具有最多不同数字算法的子方形

Question

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

根据 Daniele 的建议编辑(其他详细信息)

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

实际上我正在寻找一个在时间消耗方面更好的解决方案，因为我的解决方案被测试系统拒绝了(我超过了时间限制)。我认为它比蛮力更好，因为我没有一个一个地分析每个方 block ，但我可能是错的。不管怎样，还是不够好。

我可以附上 C++ 代码，以防它对您来说更容易，但我怀疑它是否有帮助。我只是在寻找算法建议。

Answer 1

您的算法听起来不错，O(n * n * k * log k) 时间复杂度和 O(k * k) 内存。如果您知道示例中的值是小整数，则可以通过用数组替换 map 来摆脱 log k。否则，实现该算法的代码可能效率低下。尝试在改变 n 和 k 时对代码计时，看看时间是否按预期增长。

作为另一个可能的方向，您可以尝试动态编程风格的解决方案。定义函数 f(x, y, a, b) 以计算 a x b 中的一组唯一值(可能是位图) > 矩形锚定在 (x, y)。那么问题就是求|f(x, y, k, k)|的最大值。 f(x, y, a, b) 计算为 4 个或更多更小的矩形集的并集，大约 a/2 x b/2维度。如果较小的矩形集被缓存，您将不必继续重新计算它们。缓存会占用大量内存，但您可以通过将分解安排为使用 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)的情况下得到返回。