题目描述
给你一个下标从 0 开始、大小为 m x n
的网格 image
,表示一个灰度图像,其中 image[i][j]
表示在范围 [0..255]
内的某个像素强度。另给你一个 非负 整数 threshold
。
如果 image[a][b]
和 image[c][d]
满足 |a - c| + |b - d| == 1
,则称这两个像素是 相邻像素。
区域 是一个 3 x 3
的子网格,且满足区域中任意两个 相邻 像素之间,像素强度的 绝对差 小于或等于 threshold
。
区域 内的所有像素都认为属于该区域,而一个像素 可以 属于 多个 区域。
你需要计算一个下标从 0 开始、大小为 m x n
的网格 result
,其中 result[i][j]
是 image[i][j]
所属区域的 平均 强度,向下取整 到最接近的整数。如果 image[i][j]
属于多个区域,result[i][j]
是这些区域的 “取整后的平均强度” 的 平均值,也 向下取整 到最接近的整数。如果 image[i][j]
不属于任何区域,则 result[i][j]
等于 image[i][j]
。
返回网格 result
。
样例
输入:image = [[5,6,7,10],[8,9,10,10],[11,12,13,10]], threshold = 3
输出:[[9,9,9,9],[9,9,9,9],[9,9,9,9]]
解释:图像中存在两个区域,如图片中的阴影区域所示。
第一个区域的平均强度为 9,而第二个区域的平均强度为 9.67,向下取整为 9。
两个区域的平均强度为 (9 + 9) / 2 = 9。
由于所有像素都属于区域 1 、区域 2 或两者,因此 result 中每个像素的强度都为 9。
注意,在计算多个区域的平均值时使用了向下取整的值,
因此使用区域 2 的平均强度 9 来进行计算,而不是 9.67。
输入:image = [[10,20,30],[15,25,35],[20,30,40],[25,35,45]], threshold = 12
输出:[[25,25,25],[27,27,27],[27,27,27],[30,30,30]]
解释:图像中存在两个区域,如图片中的阴影区域所示。
第一个区域的平均强度为 25 ,而第二个区域的平均强度为 30。
两个区域的平均强度为 (25 + 30) / 2 = 27.5 ,向下取整为 27。
图像中第 0 行的所有像素属于区域 1,因此 result 中第 0 行的所有像素为 25。
同理,result 中第 3 行的所有像素为 30。
图像中第 1 行和第 2 行的像素属于区域 1 和区域 2,因此它们在 result 中的值为 27。
输入:image = [[5,6,7],[8,9,10],[11,12,13]], threshold = 1
输出:[[5,6,7],[8,9,10],[11,12,13]]
解释:图像中不存在任何区域,因此对于所有像素,result[i][j] == image[i][j] 。
限制
3 <= n, m <= 500
0 <= image[i][j] <= 255
0 <= threshold <= 255
算法
(暴力枚举) $O(n^2)$
- 定义一个二维数组存储每个位置上所属区域的个数和总和。
- 暴力枚举所有
3 x 3
的子矩阵,对每个子矩阵都判定其是否为合法区域。 - 如果某个子矩阵为合法区域,则将这个区域的平均值,累加到这个子矩阵的所有位置上。
- 最后遍历每个位置,求出答案。
时间复杂度
- 子矩阵的个数为 $O(n^2)$ 个,每个子矩阵需要常数的时间遍历,故时间复杂度为 $O(n^2)$。
空间复杂度
- 需要 $O(n^2)$ 的额外空间存储每个位置上的区域个数和区域总和。
C++ 代码
class Solution {
public:
vector<vector<int>> resultGrid(vector<vector<int>>& image, int threshold) {
const int m = image.size(), n = image[0].size();
vector<vector<pair<int, int>>> t(m, vector<pair<int, int>>(n, make_pair(0, 0)));
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
auto check = [&](int x, int y) {
for (int i = x; i < x + 3; i++)
for (int j = y; j < y + 3; j++)
for (int d = 0; d < 4; d++) {
int tx = i + dx[d], ty = j + dy[d];
if (tx < x || tx >= x + 3 || ty < y || ty >= y + 3)
continue;
if (abs(image[i][j] - image[tx][ty]) > threshold)
return false;
}
return true;
};
auto sum = [&](int x, int y) {
int s = 0;
for (int i = x; i < x + 3; i++)
for (int j = y; j < y + 3; j++)
s += image[i][j];
return s;
};
auto fill = [&](int x, int y, int s) {
for (int i = x; i < x + 3; i++)
for (int j = y; j < y + 3; j++) {
t[i][j].first += s;
++t[i][j].second;
}
};
for (int i = 0; i < m - 2; i++)
for (int j = 0; j < n - 2; j++)
if (check(i, j))
fill(i, j, sum(i, j) / 9);
vector<vector<int>> ans(m, vector<int>(n));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
ans[i][j] = t[i][j].second == 0 ?
image[i][j] : t[i][j].first / t[i][j].second;
return ans;
}
};