Leetcode 661: Image Smoother

18
五月
2021

问题描述:

An image smoother is a filter of the size 3 x 3 that can be applied to each cell of an image by rounding down the average of the cell and the eight surrounding cells (i.e., the average of the nine cells in the blue smoother). If one or more of the surrounding cells of a cell is not present, we do not consider it in the average (i.e., the average of the four cells in the red smoother).

给定任意二维数组,求数组内每个格的相邻格(包括他自己)的平均值。

思路:
暴力求解法,考虑到可能的每种情况

class Solution {
    public int[][] imageSmoother(int[][] img) {
        int upperBound = 0;
        int lowerBound = img.length-1;
        int leftBound = 0;
        int rightBound = img[0].length-1;
        int[][] ans = new int[lowerBound+1][rightBound+1];
        for (int i=0; i<=lowerBound; i++){
            for(int j=0; j<=rightBound; j++){
                if(lowerBound==0){      //row vector case
                    if(rightBound==0){
                        ans[i][j]=img[i][j];
                    }
                    else{          
                        if (j==0){
                            ans[i][j]=(img[i][j]+img[i][j+1])/2;
                        }
                        else if (j==rightBound){
                            ans[i][j]=(img[i][j]+img[i][j-1])/2;
                        }
                        else{
                            ans[i][j]=(img[i][j]+img[i][j-1]+img[i][j+1])/3;
                        }
                    }
                }
                else if (rightBound==0){   //column vector case
                    if(i==0){
                        ans[i][j]=(img[i][j]+img[i+1][j])/2;
                    }
                    else if (i==lowerBound){
                        ans[i][j]=(img[i][j]+img[i-1][j])/2;
                    }
                    else{
                        ans[i][j]=(img[i][j]+img[i-1][j]+img[i+1][j])/3;
                    }
                }
                else{                     //matrix size at least 2x2
                //case 1
                if((i==0)&&(j!=0)&&(j!=rightBound)){
                    ans[i][j]=(img[i][j-1]+img[i][j]+img[i][j+1]+img[i+1][j-1]+img[i+1][j]+img[i+1][j+1])/6;
                }
                //case 2   
                else if((i==lowerBound)&&(j!=0)&&(j!=rightBound)){
                    ans[i][j]=(img[i][j-1]+img[i][j]+img[i][j+1]+img[i-1][j-1]+img[i-1][j]+img[i-1][j+1])/6;
                }
                //case 3
                else if((j==0)&&(i!=0)&&(i!=lowerBound)){
                    ans[i][j]=(img[i-1][j]+img[i-1][j+1]+img[i][j]+img[i][j+1]+img[i+1][j]+img[i+1][j+1])/6;
                }
                //case 4
                else if((j==rightBound)&&(i!=0)&&(i!=lowerBound)){
                    ans[i][j]=(img[i-1][j]+img[i-1][j-1]+img[i][j]+img[i][j-1]+img[i+1][j]+img[i+1][j-1])/6;
                }
                //case 5
                else if((i==0)&&(j==0)){
                    ans[i][j]=(img[i][j]+img[i+1][j]+img[i][j+1]+img[i+1][j+1])/4;
                }
                //case 6
                else if((i==lowerBound)&&(j==0)){
                    ans[i][j]=(img[i][j]+img[i-1][j]+img[i-1][j+1]+img[i][j+1])/4;
                }
                //case 7
                else if((i==0)&&(j==rightBound)){
                    ans[i][j]=(img[i][j]+img[i][j-1]+img[i+1][j-1]+img[i+1][j])/4;
                }
                //case 8
                else if((i==lowerBound)&&(j==rightBound)){
                    ans[i][j]=(img[i][j]+img[i][j-1]+img[i-1][j-1]+img[i-1][j])/4;
                }
                //case 9
                else{
                    ans[i][j]=(img[i][j]+img[i-1][j-1]+img[i-1][j]+img[i-1][j+1]+img[i][j-1]+img[i][j+1]+img[i+1][j-1]
                        +img[i+1][j]+img[i+1][j+1])/9;
                }
                }
            }
        }
        return ans;
    }
}

方法二:借助一个较大的辅助数组,使计算变得简单。在原数组外侧“套上一层外套”,用-1作值避免干扰。代码如下:

class Solution {
    public int[][] imageSmoother(int[][] img) {
        int original_lowerBound = img.length-1;
        int original_rightBound = img[0].length-1;
        int new_lowerBound = original_lowerBound+2;
        int new_rightBound = original_rightBound+2;
        int[][] biggerMatrix = new int[new_lowerBound+1][new_rightBound+1];
        int[][] ans = new int[original_lowerBound+1][original_rightBound+1];
        //create the new matrix with -1 surrounded
        for(int i=0; i<=new_lowerBound; i++){
            for(int j=0; j<=new_rightBound; j++){
                if((i==0)||(i==new_lowerBound)||(j==0)||(j==new_rightBound)){
                    biggerMatrix[i][j]=-1;
                }
                else{
                    biggerMatrix[i][j]=img[i-1][j-1];
                }
            }
        }
        for(int i=0; i<=original_lowerBound; i++){
            for(int j=0; j<=original_rightBound; j++){
                ans[i][j]=helper(biggerMatrix, i+1, j+1);
            }
        }
        return ans;
    }
    //utility function: given the BiggerMatrix and a corresponding index pair, return the avergae
    private int helper(int[][] matrix, int i, int j){
        int counter = 0;
        int sum = 0;
        for (int p=i-1; p<=i+1; p++){
            for (int q=j-1; q<=j+1; q++){
                if(matrix[p][q]!=-1){
                    counter++;
                    sum=sum+matrix[p][q];
                }
            }
        }
        return sum/counter;
    }
}

时间复杂度:O(mn)

TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员