C#LeetCode刷题之#661-图片平滑器（ Image Smoother）

问题

包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ，平均灰度的计算是周围的8个单元和它本身的值求平均，如果周围的单元格不足八个，则尽可能多的利用它们。

输入:
[[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

注意:

给定矩阵中的整数范围为 [0, 255]。
矩阵的长和宽的范围均为 [1, 150]。

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.

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].

示例

public class Program {

    public static void Main(string[] args) {
        int[,] nums = null;

        nums = new int[,] { { 1, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } };
        var res = ImageSmoother(nums);
        ShowArray(res);

        Console.ReadKey();
    }

    private static void ShowArray(int[,] array) {
        foreach(var num in array) {
            Console.Write($"{num} ");
        }
        Console.WriteLine();
    }

    private static int[,] ImageSmoother(int[,] M) {
        int[,] result = M.Clone() as int[,];
        for(int i = 0; i < M.GetLength(0); i++) {
            for(int j = 0; j < M.GetLength(1); j++) {
                result[i, j] = ComputerSmoothValue(M, i, j);
            }
        }
        return result;
    }

    private static int ComputerSmoothValue(int[,] M, int i, int j) {
        //以某个数为中心，求9个数的平均值即可
        //该题主要考查边界的处理
        int count = 0;
        int sum = 0;
        for(int m = Math.Max(i - 1, 0); m <= Math.Min(i + 1, M.GetLength(0) - 1); m++) {
            for(int n = Math.Max(j - 1, 0); n <= Math.Min(j + 1, M.GetLength(1) - 1); n++) {
                count++;
                sum += M[m, n];
            }
        }
        return sum / count;
    }

}

以上给出1种算法实现，以下是这个案例的输出结果：

0 0 0 0 0 0 0 0 0

分析：

假设原二维数组有m行，n列，ComputerSmoothValue的执行次数在最坏的情况会执行9次，ComputerSmoothValue执行的次数为m*n次，故以上算法的时间复杂度为：  。