ImageSmoother [source code]

public class ImageSmoother {
static
/******************************************************************************/
class Solution {
    public int[][] imageSmoother(int[][] M) {
        int m = M.length, n = M[0].length;
        int[][] res = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int count = 0, sum = 0;
                for (int k = -1; k < 2; k++) {
                    for (int t = -1; t < 2; t++) {
                        int x = i + k, y = j + t;
                        if (x >= 0 && x < m && y >= 0 && y < n) {
                            count++;
                            sum += M[x][y];
                        }
                    }
                }
                res[i][j] = sum / count;
            }
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ImageSmoother.Solution tester = new ImageSmoother.Solution();
    }
}

刚开始看到这个问题觉得好难, 因为你计算了一个cell之后, 这个cell又会影响所有其他周围的neighbor的计算; 结果最后这个题目要你做的就是一个很弱智的事情, 走一遍然后计算average就行了; 最后的速度是34ms (60%).

这里可能有一个小的优化, 有点类似sliding window的优化, 就是在计算九个数字之和的时候, 因为我们是连续计算, 所以下一个可以沿用上一个的结果, 可以减少一定的array access; 不过总体上来说这个改变的只是常数级别的, 有时间再来搞这种无关痛痒的优化了;

因为题目太新, 所以还没有discussion; 我反正觉得这个问题的描述是有问题的; 这么naive的一个计算, 完全没有办法保证最终的这个matrix所有的数字都是周围数字的average;

Problem Description

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:

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

Difficulty:Easy
Total Accepted:2.5K
Total Submissions:5K
Contributor: fallcreek
Companies
amazon
Related Topics
array