题目描述
这是 LeetCode 上的 661. 图片平滑器 ，难度为 简单。
Tag : 「模拟」、「前缀和」
图像平滑器 是大小为 3 * 33∗3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。
每个单元格的 平均灰度 定义为：该单元格自身及其周围的 88 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 99 个单元格的平均值）。
如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 44 个单元格的平均值）。
给你一个表示图像灰度的 m * nm∗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): 平均(3/4) = 平均(0.75) = 0 对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0 对于点 (1,1): 平均(8/9) = 平均(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.lengthm==img.length
- n == img[i].lengthn==img[i].length
- 1 <= m, n <= 2001<=m,n<=200
- 0 <= img[i][j] <= 2550<=img[i][j]<=255
朴素解法
为了方便，我们称每个单元格及其八连通方向单元格所组成的连通块为一个 item。
数据范围只有 200200，我们可以直接对每个 item 进行遍历模拟。
代码：
class Solution { public int[][] imageSmoother(int[][] img) { int m = img.length, n = img[0].length; int[][] ans = new int[m][n]; int[][] dirs = new int[][]{{0,0},{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}}; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { int tot = 0, cnt = 0; for (int[] di : dirs) { int nx = i + di[0], ny = j + di[1]; if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; tot += img[nx][ny]; cnt++; } ans[i][j] = tot / cnt; } } return ans; } } 复制代码
class Solution: def imageSmoother(self, img: List[List[int]]) -> List[List[int]]: m, n = len(img), len(img[0]) dirs = [[i, j] for i in range(-1, 2) for j in range(-1, 2)] ans = [[0] * n for _ in range(m)] for i in range(m): for j in range(n): tot, cnt = 0, 0 for di in dirs: nx, ny = i + di[0], j + di[1] if nx < 0 or nx >= m or ny < 0 or ny >= n: continue tot += img[nx][ny] cnt += 1 ans[i][j] = tot // cnt return ans 复制代码
- 时间复杂度：O(m * n * C)O(m∗n∗C)，其中 CC 为灰度单位所包含的单元格数量，固定为 99
- 空间复杂度：O(m * n)O(m∗n)
前缀和
在朴素解法中，对于每个 ans[i][j]ans[i][j] 我们都不可避免的遍历 88 联通方向，而利用「前缀和」我们可以对该操作进行优化。
对于某个 ans[i][j]ans[i][j] 而言，我们可以直接计算出其所在 item 的左上角 (a, b) = (i - 1, j - 1)(a,b)=(i−1,j−1) 以及其右下角 (c, d) = (i + 1, j + 1)(c,d)=(i+1,j+1)，同时为了防止超出原矩阵，我们需要将 (a, b)(a,b) 与 (c, d)(c,d) 对边界分别取 max 和 min。
当有了合法的 (a, b)(a,b) 和 (c, d)(c,d) 后，我们可以直接计算出 item 的单元格数量（所包含的行列乘积）及 item 的单元格之和（前缀和查询），从而算得 ans[i][j]ans[i][j]。
代码：
class Solution { public int[][] imageSmoother(int[][] img) { int m = img.length, n = img[0].length; int[][] sum = new int[m + 10][n + 10]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1]; } } int[][] ans = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { int a = Math.max(0, i - 1), b = Math.max(0, j - 1); int c = Math.min(m - 1, i + 1), d = Math.min(n - 1, j + 1); int cnt = (c - a + 1) * (d - b + 1); int tot = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b]; ans[i][j] = tot / cnt; } } return ans; } } 复制代码
class Solution: def imageSmoother(self, img: List[List[int]]) -> List[List[int]]: m, n = len(img), len(img[0]) sum = [[0] * (n + 10) for _ in range(m + 10)] for i in range(1, m + 1): for j in range(1, n + 1): sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1] ans = [[0] * n for _ in range(m)] for i in range(m): for j in range(n): a, b = max(0, i - 1), max(0, j - 1) c, d = min(m - 1, i + 1), min(n - 1, j + 1) cnt = (c - a + 1) * (d - b + 1) tot = sum[c + 1][d + 1] - sum[a][d + 1] - sum[c + 1][b] + sum[a][b] ans[i][j] = tot // cnt return ans 复制代码
- 时间复杂度：O(m * n)O(m∗n)
- 空间复杂度：O(m * n)O(m∗n)
同类型加餐
今日份加餐：【面试高频题】难度 1.5/5，一道「桶排序 + 前缀和」优化题 🎉 🎉
最后
这是我们「刷穿 LeetCode」系列文章的第 No.661 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
