一个 k x k 的 幻方 指的是一个 k x k 填满整数的方格阵，且每一行、每一列以及两条对角线的和 全部 相等
。幻方中的整数 不需要互不相同 。显然，每个 1 x 1 的方格都是一个幻方。
给你一个 m x n 的整数矩阵 grid ，请你返回矩阵中 最大幻方 的 尺寸 （即边长 k）。
示例 1：
**输入：** grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
**输出：** 3
**解释：** 最大幻方尺寸为 3 。
每一行，每一列以及两条对角线的和都等于 12 。
- 每一行的和：5+1+6 = 5+4+3 = 2+7+3 = 12
- 每一列的和：5+5+2 = 1+4+7 = 6+3+3 = 12
- 对角线的和：5+4+3 = 6+4+2 = 12
示例 2：
**输入：** grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
**输出：** 2
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j] <= 106
方法一：枚举正方形 + 前缀和优化
思路与算法
我们只需要按照从大到小的顺序枚举正方形的边长 edge，再枚举给定的矩阵 grid 中所有边长为 edge 的正方形，并依次判断它们是否满足幻方的要求即可。
这样做的时间复杂度是多少呢？我们记 l = \min(m, n)，那么 edge 的范围为 [1, l]，边长为 edge 的正方形有 (m-\textit{edge}+1)(n-\textit{edge}+1)=O(mn) 个，对于每个正方形，我们需要计算其每一行、列和对角线的和，一共有 edge 行 edge 列以及 2 条对角线，那么计算这些和的总时间复杂度为 ((2 \cdot \textit{edge}+2) \cdot \textit{edge})=O(l^2)。将所有项相乘，总时间复杂度即为 O(l^3 mn)。
我们无法 100% 保证 O(l^3 mn) 的算法可以在规定时间内通过所有的测试数据：虽然它的时间复杂度看起来很大，但是常数实际上很小，如果代码写得比较优秀，还是有通过的机会的。
但做一些不复杂的优化也是很有必要的。一个可行的优化点是：我们可以预处理出矩阵 grid 每一行以及每一列的前缀和，这样对于计算和的部分：
每一行只需要 O(1) 的时间即可求和，所有的 edge 行的总时间复杂度为 O(l)；
每一列只需要 O(1) 的时间即可求和，所有的 edge 列的总时间复杂度为 O(l)；
我们没有预处理对角线的前缀和，这是因为对角线只有 2 条，即使我们直接计算求和，时间复杂度也为 O(2 \cdot l) = O(l)。
因此，求和部分的总时间复杂度从 O(l^2) 降低为 O(l)，总时间复杂度降低为 O(l^2 mn)，对于本题 m, n \leq 50 的范围，该时间复杂度是合理的。
前缀和的具体实现过程可以参考下面的代码。
优化
我们只需要在 [2, l] 的范围内从大到小遍历 edge 即可，这是因为边长为 1 的正方形一定是一个幻方。
代码
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| class Solution {
public:
int largestMagicSquare(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> rowsum(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
rowsum[i][0] = grid[i][0];
for (int j = 1; j < n; ++j) {
rowsum[i][j] = rowsum[i][j - 1] + grid[i][j];
}
}
vector<vector<int>> colsum(m, vector<int>(n));
for (int j = 0; j < n; ++j) {
colsum[0][j] = grid[0][j];
for (int i = 1; i < m; ++i) {
colsum[i][j] = colsum[i - 1][j] + grid[i][j];
}
}
for (int edge = min(m, n); edge >= 2; --edge) {
for (int i = 0; i + edge <= m; ++i) {
for (int j = 0; j + edge <= n; ++j) {
int stdsum = rowsum[i][j + edge - 1] - (j ? rowsum[i][j - 1] : 0);
bool check = true;
for (int ii = i + 1; ii < i + edge; ++ii) {
if (rowsum[ii][j + edge - 1] - (j ? rowsum[ii][j - 1] : 0) != stdsum) {
check = false;
break;
}
}
if (!check) {
continue;
}
for (int jj = j; jj < j + edge; ++jj) {
if (colsum[i + edge - 1][jj] - (i ? colsum[i - 1][jj] : 0) != stdsum) {
check = false;
break;
}
}
if (!check) {
continue;
}
int d1 = 0, d2 = 0;
for (int k = 0; k < edge; ++k) {
d1 += grid[i + k][j + k];
d2 += grid[i + k][j + edge - 1 - k];
}
if (d1 == stdsum && d2 == stdsum) {
return edge;
}
}
}
}
return 1;
}
};
|
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| class Solution:
def largestMagicSquare(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
rowsum = [[0] * n for _ in range(m)]
for i in range(m):
rowsum[i][0] = grid[i][0]
for j in range(1, n):
rowsum[i][j] = rowsum[i][j - 1] + grid[i][j]
colsum = [[0] * n for _ in range(m)]
for j in range(n):
colsum[0][j] = grid[0][j]
for i in range(1, m):
colsum[i][j] = colsum[i - 1][j] + grid[i][j]
for edge in range(min(m, n), 1, -1):
for i in range(m - edge + 1):
for j in range(n - edge + 1):
stdsum = rowsum[i][j + edge - 1] - (0 if j == 0 else rowsum[i][j - 1])
check = True
for ii in range(i + 1, i + edge):
if rowsum[ii][j + edge - 1] - (0 if j == 0 else rowsum[ii][j - 1]) != stdsum:
check = False
break
if not check:
continue
for jj in range(j, j + edge):
if colsum[i + edge - 1][jj] - (0 if i == 0 else colsum[i - 1][jj]) != stdsum:
check = False
break
if not check:
continue
d1 = d2 = 0
for k in range(edge):
d1 += grid[i + k][j + k]
d2 += grid[i + k][j + edge - 1 - k]
if d1 == stdsum and d2 == stdsum:
return edge
return 1
|
复杂度分析
