题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

解题思路一

public static ArrayList<Integer> printMatrix(int[][] matrix) {
    if (matrix == null || matrix.length == 0)
        return null; //无法构成矩阵
    ArrayList<Integer> resultList = new ArrayList<Integer>();
    int time = 1;//记录绕圈的次数
    int rowLength = matrix.length;
    int colLength = matrix[0].length;
    while (colLength - time >= time - 1 && rowLength - time >= time - 1) {//仍可以绕圈
        //先横向从左向右遍历
        for (int i = time - 1; i <= colLength - time; i++) {
            resultList.add(matrix[time - 1][i]);
        }
        //第二步，有效最后一列从上到下遍历
        for (int i = time; i <= rowLength - time; i++) {
            resultList.add(matrix[i][colLength - time]);
        }
        //第三步，有效最后一行从右向左遍历
        for (int i = colLength - time - 1; i >= time - 1 && time - 1 != rowLength - time; i--) { // time - 1 != rowLength - time 避免重复输出当前行
            resultList.add(matrix[rowLength - time][i]);
        }
        //第四步，有效最先一列，从下往上遍历
        for (int i = rowLength - time - 1; i >= time && time - 1 != colLength - time; i--) { //time - 1 != colLength - time 避免输出重复列
            resultList.add(matrix[i][time - 1]);
        }
        time++;
    }
    return resultList;
}

解题思路二

想象有四根线在切割，四根线的端点前后链接，确认每次转圈遍历的范围，每转一圈，向中间聚拢，其实跟思路一一致，思路一是以点作为对象考虑，而思路二是以线对对象考虑

public static ArrayList<Integer> printMatrix2(int[][] matrix) {
    ArrayList<Integer> resultList = new ArrayList<Integer>();
    if (matrix == null || matrix.length == 0) {
        return resultList; //无法构成矩阵
    }
    int row = 0; //遍历的当前行坐标
    int rowLength = matrix.length - 1;//行坐标上界
    int col = 0; //遍历的当前列坐标
    int colLength = matrix[0].length - 1; //列坐标上界
    //想象有四根线在切割输出
    while (row <= rowLength && col <= colLength) {//仍可以绕圈
        // 一根线 0度正序输出（从左到右）
        for (int i = col; i <= colLength; i++) {
            resultList.add(matrix[row][i]);
        }
        //第二步，一根线90度正序输出（从上到下）
        for (int i = row + 1; i <= rowLength; i++) {
            resultList.add(matrix[i][colLength]);
        }
        //第三步，一根线180度逆序输出（从右到左）
        for (int i = colLength - 1; i >= col && row != rowLength; i--) { // row != rowLength 避免重复逆序输出当前行
            resultList.add(matrix[rowLength][i]);
        }
        //第四步，一根线270度逆序输出（从下到上）
        for (int i = rowLength - 1; i >= row + 1 && col != colLength; i--) { //time - 1 != colLength - time 避免输出逆序重复列
            resultList.add(matrix[i][col]);
        }
        //缩小四个点的范围
        row++;
        col++;
        rowLength--;
        colLength--;

    }
    return resultList;
}

解题思路三

类似于走迷宫，每次在一个方位走到尽头，然后循环切换下一个方位

public ArrayList<Integer> printMatrix4(int[][] matrix) {
    ArrayList<Integer> resultList = new ArrayList<Integer>();
    if (matrix == null || matrix.length == 0) {
        return resultList; //无法构成矩阵
    }
    //四个方位的坐标变化
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    int x = 0; //当前行坐标
    int y = 0; //当前列坐标
    int rowLength = matrix.length - 1; //行坐标上界
    int colLength = matrix[0].length - 1; //列坐标上界
    int dir = 0; //初始行走方位
    boolean[][] flag = new boolean[rowLength + 1][colLength + 1];//记录每个位置是否走过
    while (x >= 0 && x <= rowLength && y >= 0 && y <= colLength && !flag[x][y]) {
        resultList.add(matrix[x][y]);
        flag[x][y] = true;//已走过
        //把当前方位的格子全部走完
        while (x + dx[dir] >= 0 && x + dx[dir] <= rowLength && y + dy[dir] >= 0 && y + dy[dir] <= colLength && !flag[x + dx[dir]][y + dy[dir]]) {
            x += dx[dir]; //移动到一个方位
            y += dy[dir];
            resultList.add(matrix[x][y]);
            flag[x][y] = true;
        }
        //当前方位走完，换下一方位
        dir = (dir + 1) % 4;
        x += dx[dir];
        y += dy[dir];
    }
    return resultList;

}