leetcode-661-Image Smoother

chenjx85

发布于 2018-07-05 16:14:47

6660

发布于 2018-07-05 16:14:47

文章被收录于专栏：chenjx85的技术专栏 chenjx85的技术专栏chenjx85的技术专栏

题目描述：

Given a 2D integer matrix M representing the gray scale of an image, you need to design a smoother to make the gray scale of each cell becomes the average gray scale (rounding down) of all the 8 surrounding cells and itself. If a cell has less than 8 surrounding cells, then use as many as you can.

Example 1:

Input:
[[1,1,1],
 [1,0,1],
 [1,1,1]]
Output:
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
Explanation:
For the point (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the point (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

Note:

The value in the given matrix is in the range of [0, 255].
The length and width of the given matrix are in the range of [1, 150].

要完成的函数：

vector<vector<int>> imageSmoother(vector<vector<int>>& M)

说明：

1、给定一个二维vector，将其看做是一张图像，对这张图像做平均滤波，也就是每个像素点的值等于(本身的值+周围8个像素点的值)/9。

如果周围没有8个像素，那么尽可能多地采集像素点，比如四个边角，每个边角有4个可计算的点，比如4条边上非边角的像素点，每个点有6个可计算的点。

返回平均滤波得到的二维矩阵，如果除法得到的是小数，那么向下取整。

2、这道题很容易，暴力解法就可以解决。

笔者最开始想要精细化处理，写的代码复杂一些，但是可以降低时间复杂度。

后来觉得实在太麻烦了，不如暴力解法就好，参考了评论区的想法，自己实现了一遍代码，如下：（附详解）

    int avg(int i,int j,vector<vector<int>>&M)//这里一定要加上&，不加重新复制了一遍M，慢了很多
    {
        int sum=0,count=0;
        for(int x=-1;x<=1;x++)
        {
            if(i+x>=0&&i+x<M.size())//前一个条件针对于第一行，后一个条件针对于最后一行
            {
                for(int y=-1;y<=1;y++)
                {
                    if(j+y>=0&&j+y<M[0].size())//前一个条件针对于第一列，后一个条件针对于最后一列
                    {
                        sum+=M[i+x][j+y];
                        count++;
                    }
                }
            }
        }
        return (sum/count);
    }
    
    vector<vector<int>> imageSmoother(vector<vector<int>>& M) 
    {
        int hang=M.size(),lie=M[0].size(),result;
        vector<int>res1(lie,0);
        vector<vector<int>>res(hang,res1);//定义一个和M同样行数同样列数的矩阵res
        for(int i=0;i<hang;i++)
        {
            for(int j=0;j<lie;j++)
                res[i][j]=avg(i,j,M);//对res中的每个值进行处理
        }
        return res;
    }

上述代码中唯一要注意的点就是avg函数的参数矩阵，要加上&，不然会重新复制一份矩阵M，慢了很多。

上述代码实测176ms，beats 85.93% of cpp submissions。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-06-15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

其他

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

其他

登录后参与评论

0 条评论

热度