0661. 图片平滑器

题目地址(661. 图片平滑器)

https://leetcode-cn.com/problems/image-smoother/

题目描述

图像平滑器 是大小为 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): 平均(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

前置知识

公司

• 暂无

思路

简单思路就是统计以每个点 (i, j) 为中心的周围八个点的数值和，然后计算平均数更新答 案 ans，最后返回 ans 即可。

注意到遍历过程需要更新，于是新建一个数组可以避免这种情况。注意到 img[i][j] 值都 介于 0-255 之间，因此使用 int 的低八位存储值，9-16 位存储新值的原地算法也是可以 的，感兴趣的可以试下。

注意到前面我们需要计算数值和，因此二维前缀和也是可以节省时间的。只不过题目明确了 是周围八个点的和，因此节省的时间也是常数，复杂度不变。

前缀和我直接复制的我 的[刷题插件](力扣刷题插件的模板 ，没改直接用的。

image.png

关键点

• 位运算

• 前缀和

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def imageSmoother(self, matrix: List[List[int]]) -> List[List[int]]:
        m,n = len(matrix), len(matrix[0])
        # 建立
        pre = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m+1):
            for j in range(1, n +1):
                pre[i][j] = pre[i-1][j]+ pre[i][j-1] - pre[i-1][j-1] + matrix[i-1][j-1]
        ans = [[0 for _ in range(n)] for _ in range(m)]
        # 使用，等价于以(x1,y1)为矩阵左上角以(x2,y2)为矩阵右下角的所有格子的和
        for i in range(m):
            for j in range(n):
                x1,y1,x2,y2 = max(0, i-1),max(0, j-1),min(m-1, i+1),min(n-1, j+1)
                cnt = (y2 - y1 + 1) * (x2 - x1 + 1)
                ans[i][j] = (pre[x2+1][y2+1] + pre[x1][y1] - pre[x1][y2+1] - pre[x2+1][y1])//cnt
        return ans

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(m*n)$

• 空间复杂度：$O(m*n)$ 可以原地算法优化到 O(1)

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时 间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回 答。更多算法套路可以访问我的 LeetCode 题解仓库 ：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关 注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你 识别套路，高效刷题。