这是在一次面试中被问到的问题。我想知道获得预期结果的最佳优化算法。问题是，假设你有一个(n x m)矩阵里面有一些数字。现在，您必须计算大小>= (2 x 2)的矩阵的个数，这将满足以下两个条件:
- 应该至少有两个1;
- 矩阵的两个角元相等。
我知道取矩阵2 × 2及以上的所有元素的蛮力算法;然后数数字。检查角元素的6个可能条件其中任意两个相等。我想知道如何处理这些问题或任何来源，因为我无法在"GeeksForGeeks"或StackOverFlow本身找到任何东西，以最优化的方式。
这是一个优化方式的提示。
首先构建一个(n,m)矩阵，计算1在(1-i, 1-j)子矩阵中的个数:nm个操作，nm个内存
现在对于矩阵的每个元素，搜索在
之后等于 的所有元素- 如果在同一行，你可以使用下面的任何一行来创建一个有两个角等于 的矩阵
- 如果在同一列，你可以使用任何列之后有一个矩阵的两个角等于
- 如果既不在同一行也不在同列那么只有一个矩阵有两个角等于
- 预计算的等效矩阵的极角元素之差为子矩阵 中元素的个数。
- 一旦一个子矩阵中包含超过2个子矩阵，包括它在内的所有子矩阵也将具有:您可以使用它来短路完整分析
以上只是粗略的边缘，还有一些设计算法的工作，但对于足够大的矩阵，它应该比蛮力好一点…