文章目录
问题描述
-
给你一个 n x n 的二维数组 grid，它包含范围 [0, n2 - 1] 内的不重复元素。
-
实现 neighborSum 类：
-
neighborSum(int [][]grid) 初始化对象。
-
int adjacentSum(int value) 返回在 grid 中与 value 相邻的元素之和，相邻指的是与 value 在上、左、右或下的元素。
-
int diagonalSum(int value) 返回在 grid 中与 value 对角线相邻的元素之和，对角线相邻指的是与 value 在左上、右上、左下或右下的元素。
解决思路
-
用一个长为 8 的数组存放偏移向量，前 4 个表示上下左右四个方向，后 4 个表示斜向的四个方向。
-
用一个大小为 n2×2 的数组 s 预处理元素和，其中 s[v][0] 为 adjacentSum(v) 的结果，s[v][1] 为 diagonalSum(v) 的结果。这可以在初始化时，遍历 grid[i][j] 以及偏移向量，累加每个元素的相邻元素之和计算出来。
代码示例
class NeighborSum {
static constexpr int dirs[8][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, 1}, {-1, -1}, {1, -1}};
vector<array<int, 2>> s;
public:
NeighborSum(vector<vector<int>>& grid) {
int n = grid.size();
s.resize(n * n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int v = grid[i][j];
for (int k = 0; k < 8; k++) {
int x = i + dirs[k][0], y = j + dirs[k][1];
if (0 <= x && x < n && 0 <= y && y < n) {
s[v][k / 4] += grid[x][y];
}
}
}
}
}
int adjacentSum(int value) {
return s[value][0];
}
int diagonalSum(int value) {
return s[value][1];
}
};
复杂度分析
- 时间复杂度：初始化 O(n2)，其余 O(1)，其中 n 为 grid 的行数和列数。
- 空间复杂度：初始化 O(n2)，其余 O(1)。