661. 图片平滑器 :「模拟」&「前缀和」-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

题目描述

这是 LeetCode 上的 661. 图片平滑器 ，难度为简单。

Tag : 「模拟」、「前缀和」

图像平滑器是大小为 $3 * 3$ 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。

每个单元格的平均灰度定义为：该单元格自身及其周围的 $8$ 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 $9$ 个单元格的平均值）。

如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 $4$ 个单元格的平均值）。

给你一个表示图像灰度的 $m * 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.length$
$n == img[i].length$
$1 <= m, n <= 200$
$0 <= img[i][j] <= 255$

朴素解法

为了方便，我们称每个单元格及其八连通方向单元格所组成的连通块为一个 item。

数据范围只有 $200$ ，我们可以直接对每个 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)$ ，其中 $C$ 为灰度单位所包含的单元格数量，固定为 $9$
空间复杂度： $O(m * n)$

前缀和

在朴素解法中，对于每个 $ans[i][j]$ 我们都不可避免的遍历 $8$ 联通方向，而利用「前缀和」我们可以对该操作进行优化。

对于某个 $ans[i][j]$ 而言，我们可以直接计算出其所在 item 的左上角 $(a, b) = (i – 1, j – 1)$ 以及其右下角 $(c, d) = (i + 1, j + 1)$ ，同时为了防止超出原矩阵，我们需要将 $(a, b)$ 与 $(c, d)$ 对边界分别取 max 和 min。

当有了合法的 $(a, b)$ 和 $(c, d)$ 后，我们可以直接计算出 item 的单元格数量（所包含的行列乘积）及 item 的单元格之和（前缀和查询），从而算得 $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
复制代码