欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

逆时针矩阵

程序员文章站 2022-05-24 20:10:24
...
最近在http://suanfa.group.iteye.com/group/topic/27110看到一个逆时针矩阵。大致意思是说如果给定M*N的矩阵,在矩阵中采用逆时针方式填充数据。比如

3*3矩阵结果是:
1  8  7
2  9  6
3  4  5
3*4矩阵结果是:
1 10  9  8
2 11 12  7
3  4  5  6
4*6矩阵结果是:
1 16 15 14 13 12
2 17 24 23 22 11
3 18 19 20 21 10
4  5  6  7  8  9
6*4矩阵结果是:
1 16 15 14
2 17 24 13
3 18 23 12
4 19 22 11
5 20 21 10
6  7  8  9

这种问题首先想到的是个数学问题,最好的办法是总结出规律,直接定位。如
f(x,y)=z (其中x,y是矩阵的坐标,z是对应的数值,如 f(2,3)=19表示第3行第4列的值是19),只要找到这样的f函数即可。

另外这个方法符合递归的特性,比如最外面一圈的数据(一个长方形)与第二圈的数据(也是一个长方形)有相同的特性,都是按“下-->右-->上-->左”的方式填充的,左上角数据最小,第一行第二个数据最大,...。这样就可以用递归的方式来实现了“先填充外层矩形,如果矩形不是空心的,再递归填充里面的矩阵”。

还有一种方法是按题目的说法(逆时针输出),用模拟的方法来实现,“当前位置填充--->找到下一位置--->当前位置填充--->找到下一位置-->...”由于数据是连续的,每次只要找到“下一个填充位置”就可以了。下一位置怎么找?与当前填充方向有关。即有4种填充策略,每个填充完后返回下一个要使用的策略。

实际应用中应该优先考虑第一种方法,这样效率极高。
第二种方法也还可以,代码应该会比较简洁。
我这里对第三种方法进行了尝试,完整代码如下
public class Dir {
    public class Position{
        public int row; 
        public int col; 
        public Position(int row,int col){
            this.row=row;
            this.col=col;
        }
    }
    public static final Dir DOWN=new Dir(){
        protected Dir getNext() {
            return Dir.RIGHT;
        }
        public Dir fill(int[][] arr,Position pos) {
            int temp=arr[pos.row][pos.col];
            pos.row++;
            //从当前位置往下填充所有为0的单元格,遇到不为0(表示已经填充过了)时停止
            for(int i=pos.row,len=arr.length;i<len;i++){
                if(arr[i][pos.col]==0){
                    arr[i][pos.col]=++temp;
                    pos.row=i;
                }else{
                    break;
                }
            }
            return this.nextDir(arr, pos);
        }
    };
    public static final Dir RIGHT=new Dir(){
        protected Dir getNext() {
            return Dir.UP;
        }
        public Dir fill(int[][] arr,Position pos) {
            int temp=arr[pos.row][pos.col];
            pos.col++;
            //从当前位置往右填充所有为0的单元格,遇到不为0(表示已经填充过了)时停止
            for(int i=pos.col,len=arr[0].length;i<len;i++){
                if(arr[pos.row][i]==0){
                    arr[pos.row][i]=++temp;
                    pos.col=i;
                }else{
                    break;
                }
            }
            return this.nextDir(arr, pos);
        }
    };
    public static final Dir UP=new Dir(){
        protected Dir getNext() {
            return Dir.LEFT;
        }
        public Dir fill(int[][] arr,Position pos) {
            int temp=arr[pos.row][pos.col];
            pos.row--;
            //从当前位置往上填充所有为0的单元格,遇到不为0(表示已经填充过了)时停止
            for(int i=pos.row;i>=0;i--){
                if(arr[i][pos.col]==0){
                    arr[i][pos.col]=++temp;
                    pos.row=i;
                }else{
                    break;
                }
            }
            return this.nextDir(arr, pos);
        }
    };
    public static final Dir LEFT=new Dir(){
        protected Dir getNext() {
            return Dir.DOWN;
        }
        public Dir fill(int[][] arr,Position pos) {
            int temp=arr[pos.row][pos.col];
            pos.col--;
            //从当前位置往左填充所有为0的单元格,遇到不为0(表示已经填充过了)时停止
            for(int i=pos.col;i>=0;i--){
                if(arr[pos.row][i]==0){
                    arr[pos.row][i]=++temp;
                    pos.col=i;
                }else{
                    break;
                }
            }
            return this.nextDir(arr, pos);
        }
    };
    public Dir fill(int[][] arr,Position pos){
        return null;// to be implemented
    }
    /** 下一个方向是什么 */
    protected Dir getNext() {
        return null;// to be implemented
    }
    protected Dir nextDir(int[][] arr,Position pos){
        return (arr[pos.row][pos.col]==arr.length*arr[0].length)?null:this.getNext();
    }
    
}


测试代码如下
public class Test {

    public static void main(String[] args) {
        // 4行6列的数组
        int M = 4, N = 6;
        int[][] arr = new int[M][N];
        arr[0][0] = 1;
        //初始方向向下
        Dir d = Dir.DOWN;
        //初始位置左上角
        Position pos = d.new Position(0,0);
        //开始填充
        do {
            d = d.fill(arr, pos);
        } while (d != null);
        //输出结果
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print((arr[i][j] < 10 ?" ":"")+arr[i][j]+" ");
            }
            System.out.println();
        }
    }
}


运行结果为:
1 16 15 14 13 12
2 17 24 23 22 11
3 18 19 20 21 10
4  5  6  7  8  9
完全正常。

以上代码中使用了“模板方法模式+变种的单例模式(4个实例)”。还有“匿名内部类”的使用。
相关标签: java 算法