661. 图片平滑器
661. 图片平滑器
题目
An image smoother is a filter of the size 3 x 3 that can be applied to each cell of an image by rounding down the average of the cell and the eight surrounding cells (i.e., the average of the nine cells in the blue smoother). If one or more of the surrounding cells of a cell is not present, we do not consider it in the average (i.e., the average of the four cells in the red smoother).
Given an m x n integer matrix img representing the grayscale of an image, return the image after applying the smoother on each cell of it.
Example 1:
Input: img = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0
Example 2:
Input: img = [[100,200,100],[200,50,200],[100,200,100]]
Output: [[137,141,137],[141,138,141],[137,141,137]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor((100+200+200+50)/4) = floor(137.5) = 137
For the points (0,1), (1,0), (1,2), (2,1): floor((200+200+50+200+100+100)/6) = floor(141.666667) = 141
For the point (1,1): floor((50+200+200+200+200+100+100+100+100)/9) = floor(138.888889) = 138
Constraints:
m == img.lengthn == img[i].length1 <= m, n <= 2000 <= img[i][j] <= 255
题目大意
图像平滑器 是大小为 3 x 3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。
每个单元格的 平均灰度 定义为：该单元格自身及其周围的 8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 9 个单元格的平均值）。
如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 4 个单元格的平均值）。
给你一个表示图像灰度的 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.lengthn == img[i].length1 <= m, n <= 2000 <= img[i][j] <= 255
解题思路
思路一：基础版
创建新数组： 首先创建一个新的二维数组
smoothImg，其大小与输入的图像数组img相同。这个数组用于存储平滑后的像素值。遍历图像每个像素：
对于每个像素
(i, j)，需要检查其邻居。包括当前像素自己以及其上、下、左、右和四个对角方向的像素。 注意：需要确保索引在图像的有效范围内，避免越界。计算邻居的平均值：
对每个像素，遍历其周围的 8 个方向的像素，并累加这些有效邻居的值。每累加一个有效邻居，就增加计数器
count，用来记录有效的邻居个数。存储结果：
计算得到每个像素周围邻居的平均值（用
Math.floor向下取整），并将其存入smoothImg[i][j]。返回结果： 最终返回
smoothImg，即经过平滑处理后的图像。
复杂度分析
- 时间复杂度：
O(m * n)，需要遍历每个像素并计算其邻居。 - 空间复杂度：
O(m * n)，使用了额外的二维数组smoothImg来存储结果。
思路二：优化版
创建临时数组
temp： 可以通过减少空间复杂度的方式，避免创建额外的二维数组。这个优化版的核心思想是通过临时保存当前行的像素值（temp和preVal）来减少重复访问。遍历图像每个像素：
- 遍历每个像素
(i, j)时，计算其周围的邻居，并计算这些邻居的和与个数。 - 在遍历过程中，不再创建新的二维数组，而是直接在输入数组上修改值。
- 遍历每个像素
计算邻居的平均值：
- 对每个像素，遍历其周围的有效邻居，计算邻居的值的和，并计算邻居的个数。
更新结果：
- 使用
Math.floor取整计算平滑后的值，并更新原数组中的值。
- 使用
返回结果：
- 最终返回处理过的原数组
img，该数组已经被更新为平滑后的值。
- 最终返回处理过的原数组
复杂度分析
- 时间复杂度：
O(m * n)，与思路一相同。 - 空间复杂度：
O(n)，只使用了一个一维数组temp来存储上一行的像素，从而降低了空间复杂度。
代码
var imageSmoother = function (img) {
const m = img.length; // 图像行数
const n = img[0].length; // 图像列数
const smoothImg = new Array(m).fill(0).map(() => new Array(n).fill(0)); // 创建新图像
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let sum = 0;
let count = 0;
// 遍历当前像素的8个邻居
for (let x = i - 1; x <= i + 1; x++) {
for (let y = j - 1; y <= j + 1; y++) {
// 判断邻居是否在有效范围内
if (0 <= x && x < m && 0 <= y && y < n) {
sum += img[x][y];
count += 1;
}
}
}
// 将平滑后的值存入新图像
smoothImg[i][j] = Math.floor(sum / count);
}
}
return smoothImg; // 返回处理后的图像
};
var imageSmoother = function (img) {
const m = img.length; // 图像行数
const n = img[0].length; // 图像列数
const temp = new Array(n); // 临时数组，用于存储上一行像素
let preVal = 0; // 用于存储上一行当前像素值
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
let sum = 0;
let count = 0;
// 处理下方邻居（i+1行）
if (i + 1 < m) {
if (j - 1 >= 0) {
sum += img[i + 1][j - 1];
count += 1;
}
sum += img[i + 1][j];
count += 1;
if (j + 1 < n) {
sum += img[i + 1][j + 1];
count += 1;
}
}
// 处理当前行的邻居（i行）
if (j - 1 >= 0) {
sum += temp[j - 1];
count += 1;
}
sum += img[i][j];
count += 1;
if (j + 1 < n) {
sum += img[i][j + 1];
count += 1;
}
// 处理上方邻居（i-1行）
if (i - 1 >= 0) {
if (j - 1 >= 0) {
sum += preVal;
count += 1;
}
sum += temp[j];
count += 1;
if (j + 1 < n) {
sum += temp[j + 1];
count += 1;
}
preVal = temp[j];
}
temp[j] = img[i][j]; // 更新当前行像素到temp
img[i][j] = Math.floor(sum / count); // 更新原数组为平滑后的值
}
}
return img; // 返回修改后的图像
};