Easy
题目描述
图像平滑器是一个大小为 3 x 3 的过滤器，可以应用于图像的每个单元格，通过对该单元格和周围八个单元格的平均值向下取整来实现（即蓝色平滑器中九个单元格的平均值）。如果一个单元格的一个或多个周围单元格不存在，我们不会在平均值中考虑它（即红色平滑器中四个单元格的平均值）。
给定一个 m x n 的整数矩阵 img 表示图像的灰度，返回应用平滑器后的图像。
示例 1：
输入：img = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[0,0,0],[0,0,0],[0,0,0]]
解释：
对于点 (0,0), (0,2), (2,0), (2,2)：floor(3/4) = floor(0.75) = 0
对于点 (0,1), (1,0), (1,2), (2,1)：floor(5/6) = floor(0.83333333) = 0
对于点 (1,1)：floor(8/9) = floor(0.88888889) = 0
示例 2：
输入：img = [[100,200,100],[200,50,200],[100,200,100]]
输出：[[137,141,137],[141,138,141],[137,141,137]]
解释：
对于点 (0,0), (0,2), (2,0), (2,2)：floor((100+200+200+50)/4) = floor(137.5) = 137
对于点 (0,1), (1,0), (1,2), (2,1)：floor((200+200+50+200+100+100)/6) = floor(141.666667) = 141
对于点 (1,1)：floor((50+200+200+200+200+100+100+100+100)/9) = floor(138.888889) = 138
提示：
- m == img.length
- n == img[i].length
- 1 <= m, n <= 200
- 0 <= img[i][j] <= 255
解题思路
这道题的核心思路是对图像矩阵中每个位置进行 3x3 邻域的平均值计算。
解题思路：
遍历每个位置：对于原矩阵中的每个位置 (i, j)，我们需要计算其 3x3 邻域的平均值。
边界处理：关键在于处理边界情况。对于边界上的位置，其 3x3 邻域可能不完整，我们只计算存在的邻居的平均值。
计算邻域均值：
- 遍历以 (i, j) 为中心的 3x3 区域，即从 (i-1, j-1) 到 (i+1, j+1)
- 检查每个邻居位置是否在矩阵边界内
- 累加有效邻居的值，并记录有效邻居的数量
- 计算平均值并向下取整
创建新矩阵：为了避免修改原矩阵影响后续计算，需要创建一个新的结果矩阵。
算法步骤：
- 创建与原矩阵相同大小的结果矩阵
- 对每个位置 (i, j)：
- 初始化总和 sum 和计数 count
- 遍历 3x3 邻域 (dx, dy) ∈ {-1, 0, 1} × {-1, 0, 1}
- 检查邻居位置 (i+dx, j+dy) 是否有效
- 累加有效邻居值和计数
- 计算 sum/count 的整数部分
代码实现
class Solution {
public:
vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
int m = img.size();
int n = img[0].size();
vector<vector<int>> result(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int sum = 0;
int count = 0;
// 遍历3x3邻域
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
int ni = i + di;
int nj = j + dj;
// 检查边界
if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
sum += img[ni][nj];
count++;
}
}
}
result[i][j] = sum / count;
}
}
return result;
}
};
class Solution:
def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
m, n = len(img), len(img[0])
result = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
sum_val = 0
count = 0
# 遍历3x3邻域
for di in range(-1, 2):
for dj in range(-1, 2):
ni, nj = i + di, j + dj
# 检查边界
if 0 <= ni < m and 0 <= nj < n:
sum_val += img[ni][nj]
count += 1
result[i][j] = sum_val // count
return result
public class Solution {
public int[][] ImageSmoother(int[][] img) {
int m = img.Length;
int n = img[0].Length;
int[][] result = new int[m][];
for (int i = 0; i < m; i++) {
result[i] = new int[n];
for (int j = 0; j < n; j++) {
int sum = 0;
int count = 0;
// 遍历3x3邻域
for (int di = -1; di <= 1; di++) {
for (int dj = -1; dj <= 1; dj++) {
int ni = i + di;
int nj = j + dj;
// 检查边界
if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
sum += img[ni][nj];
count++;
}
}
}
result[i][j] = sum / count;
}
}
return result;
}
}
var imageSmoother = function(img) {
const m = img.length;
const n = img[0].length;
const result = Array(m).fill(0).map(() => Array(n).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let sum = 0;
let count = 0;
// 遍历3x3邻域
for (let di = -1; di <= 1; di++) {
for (let dj = -1; dj <= 1; dj++) {
const ni = i + di;
const nj = j + dj;
// 检查边界
if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
sum += img[ni][nj];
count++;
}
}
}
result[i][j] = Math.floor(sum / count);
}
}
return result;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(m × n) - 需要遍历每个位置，每个位置检查最多9个邻居 |
| 空间复杂度 | O(m × n) - 需要创建一个新的结果矩阵 |