|
| 1 | +# Time: O(m * n) |
| 2 | +# Space: O(1) |
| 3 | + |
| 4 | +# Given a 2D integer matrix M representing the gray scale of an image, |
| 5 | +# you need to design a smoother to make the gray scale of each cell becomes |
| 6 | +# the average gray scale (rounding down) of all the 8 surrounding cells and itself. |
| 7 | +# If a cell has less than 8 surrounding cells, then use as many as you can. |
| 8 | +# |
| 9 | +# Example 1: |
| 10 | +# Input: |
| 11 | +# [[1,1,1], |
| 12 | +# [1,0,1], |
| 13 | +# [1,1,1]] |
| 14 | +# Output: |
| 15 | +# [[0, 0, 0], |
| 16 | +# [0, 0, 0], |
| 17 | +# [0, 0, 0]] |
| 18 | +# Explanation: |
| 19 | +# For the point (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0 |
| 20 | +# For the point (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0 |
| 21 | +# For the point (1,1): floor(8/9) = floor(0.88888889) = 0 |
| 22 | +# Note: |
| 23 | +# The value in the given matrix is in the range of [0, 255]. |
| 24 | +# The length and width of the given matrix are in the range of [1, 150]. |
| 25 | + |
| 26 | +class Solution(object): |
| 27 | + def imageSmoother(self, M): |
| 28 | + """ |
| 29 | + :type M: List[List[int]] |
| 30 | + :rtype: List[List[int]] |
| 31 | + """ |
| 32 | + def getGray(M, i, j): |
| 33 | + directions = [[-1, -1], [0, -1], [1, -1], \ |
| 34 | + [-1, 0], [0, 0], [1, 0], \ |
| 35 | + [-1, 1], [0, 1], [1, 1]] |
| 36 | + |
| 37 | + total, count = 0, 0.0 |
| 38 | + for direction in directions: |
| 39 | + ii, jj = i + direction[0], j + direction[1] |
| 40 | + if 0 <= ii < len(M) and 0 <= jj < len(M[0]): |
| 41 | + total += M[ii][jj] |
| 42 | + count += 1.0 |
| 43 | + return int(total / count) |
| 44 | + |
| 45 | + result = [[0 for _ in xrange(len(M[0]))] for _ in xrange(len(M))] |
| 46 | + for i in xrange(len(M)): |
| 47 | + for j in xrange(len(M[0])): |
| 48 | + result[i][j] = getGray(M, i, j); |
| 49 | + return result |
0 commit comments