手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

Leetcode 661: Image Smoother

时间:2021/5/18 5:36:32|来源:|点击: 次

问题描述:

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)

Copyright © 2002-2019 某某自媒体运营 版权所有