Java solution--linear time and O(1) space


  • 0
    W

    I think the main point of this problem is to update M in place. Since the range of each element is in[0,255], the average must be in this range too. Thus, we can use higher bits to store the average for each step, and use the lower 8 bits to keep the original value of M[i][j]. After everything is done, we iterate again to move the higher bits into the lower 8bits to reflect the value of the average.

    class Solution {
        int[] dx=new int[]{-1,-1,-1,0,0,0,1,1,1};
        int[] dy=new int[]{-1,0,1,-1,0,1,-1,0,1};
        public int[][] imageSmoother(int[][] M) {
            int m=M.length, n=M[0].length;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    updateM(M,i,j);
                }
            }
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    M[i][j]=M[i][j]/256;
                }
            }
            return M;
        }
        private void updateM(int[][]M, int i, int j){
            int num=0;
            int sum=0;
            for(int ind=0;ind<9;ind++){
                int nexti=i+dx[ind], nextj=j+dy[ind];
                if(nexti>=0&&nexti<M.length&&nextj>=0&&nextj<M[0].length){
                    num++;
                    sum+=M[nexti][nextj]%256;
                }
            }
            M[i][j]+=sum/num*256;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.