【面试题】顺时针打印矩阵（两种解法 Java实现）题目描述

93 阅读 0 评论 62 点赞

我是靠谱客的博主轻松香烟，这篇文章主要介绍【面试题】顺时针打印矩阵（两种解法 Java实现）题目描述，现在分享给大家，希望可以做个参考。

题目描述

在这里插入图片描述
由于是以从外圈到内圈的顺序依次打印，我们可以把矩阵想象成若⼲个圈，循环打印，每次打印一个圈，循环结束的条件是当前圈的左上角坐标（startX，startY）满足 startX*2 >= cols && startY*2 >= rows

我们可以把顺时针打印⼀圈分为四步走：

第⼀步从左到右打印⼀⾏，
第⼆步从上到下打印⼀列，
第三步从右到左打印⼀⾏，
第四步从下到上打印⼀列。

在这里插入图片描述
不过，要注意的是，最后⼀圈有可能退化成只有⼀⾏、只有⼀列，甚⾄只有⼀个数字，此时打印这样的⼀圈就不再需要四步。

因此每⼀步我们要先判断一下是否需要打印的前提条件，再根据起始坐标和终⽌坐标⽤⼀个循环就能打印出⼀⾏或者⼀列。

Java

复制代码

class Solution {
    int[] res; // 声明最终返回结果的 int数组 
    int count = 0; // 结果数组中的下标计数

public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0)
            return new int[0];
        int start = 0; // 每一圈的左上角坐标为（start，start）
        int rows = matrix.length;
        int cols = matrix[0].length;
        res = new int[matrix.length * matrix[0].length];

while (rows > start*2 && cols > start*2){ 
            printMatrixInCircle(matrix, rows, cols, start);
            start++;
        }
        return res;
    }

public void printMatrixInCircle(int[][] matrix, int rows, int cols, int start) {
        int endX = cols-start-1;
        int endY = rows-start-1;
        // 从左到右打印一行
        for (int i=start; i<=endX; i++)
            res[count++] = matrix[start][i];

// 从上到下打印一列，前提条件是终止行号>起始行号
        if (endY > start) {
            for (int i=start+1; i<=endY; i++)
                res[count++] = matrix[i][endX]; 
        }

// 从右到左打印一行，前提条件是终止行号>起始行号，且终止列号>起始列号
        if (endY > start && endX > start) {
            for (int i=endX-1; i>=start; i--)
                res[count++] = matrix[endY][i];
        }

// 从下到上打印一列，前提条件是至少有三行两列，即终止行号-1 >起始行号，且终止列号>起始列号
        if (endY-1 > start && endX > start) {
            for (int i=endY-1; i>start; i--)
                res[count++] = matrix[i][start];
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    int[] res; // 声明最终返回结果的 int数组 
    int count = 0; // 结果数组中的下标计数

    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0)
            return new int[0];
        int start = 0; // 每一圈的左上角坐标为（start，start）
        int rows = matrix.length;
        int cols = matrix[0].length;
        res = new int[matrix.length * matrix[0].length];

        while (rows > start*2 && cols > start*2){ 
            printMatrixInCircle(matrix, rows, cols, start);
            start++;
        }
        return res;
    }

    public void printMatrixInCircle(int[][] matrix, int rows, int cols, int start) {
        int endX = cols-start-1;
        int endY = rows-start-1;
        // 从左到右打印一行
        for (int i=start; i<=endX; i++)
            res[count++] = matrix[start][i];

        // 从上到下打印一列，前提条件是终止行号>起始行号
        if (endY > start) {
            for (int i=start+1; i<=endY; i++)
                res[count++] = matrix[i][endX]; 
        }

        // 从右到左打印一行，前提条件是终止行号>起始行号，且终止列号>起始列号
        if (endY > start && endX > start) {
            for (int i=endX-1; i>=start; i--)
                res[count++] = matrix[endY][i];
        }

        // 从下到上打印一列，前提条件是至少有三行两列，即终止行号-1 >起始行号，且终止列号>起始列号
        if (endY-1 > start && endX > start) {
            for (int i=endY-1; i>start; i--)
                res[count++] = matrix[i][start];
        }
    }
}

另一种写法，考虑上下左右四个边界，不断向内收缩，当边界缩小到相遇（下边界>上边界或者左边界>右边界）时，则跳出循环，打印完毕。

Java

复制代码

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0)
            return new int[0];
        // 初始化上、下、左、右四个边界
        int top = 0, bottom = matrix.length -1, left = 0, right = matrix[0].length -1;
        // 定义返回数组，及其下标索引变量
        int[] res = new int[matrix.length * matrix[0].length];
        int index = 0;

while (true) {
            for(int i=left; i<=right; i++) // 从左到右打印一行
                res[index++] = matrix[top][i];
            top++; // 上边界向内收缩
            if (top > bottom) break; // 判断边界是否相遇
            
            for(int i=top; i<=bottom; i++) // 从上到下打印一列
                res[index++] = matrix[i][right];
            right--; // 右边界向内收缩
            if (right < left) break; // 判断边界是否相遇

for(int i=right; i>=left; i--) // 从右到左打印一行
                res[index++] = matrix[bottom][i];
            bottom--; // 下边界向内收缩
            if (bottom < top) break; // 判断边界是否相遇

for(int i=bottom; i>=top; i--) // 从下到上打印一列
                res[index++] = matrix[i][left];
            left++; // 左边界向内收缩
            if (left > right) break; // 判断边界是否相遇
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0)
            return new int[0];
        // 初始化上、下、左、右四个边界
        int top = 0, bottom = matrix.length -1, left = 0, right = matrix[0].length -1;
        // 定义返回数组，及其下标索引变量
        int[] res = new int[matrix.length * matrix[0].length];
        int index = 0;

        while (true) {
            for(int i=left; i<=right; i++) // 从左到右打印一行
                res[index++] = matrix[top][i];
            top++; // 上边界向内收缩
            if (top > bottom) break; // 判断边界是否相遇
            
            for(int i=top; i<=bottom; i++) // 从上到下打印一列
                res[index++] = matrix[i][right];
            right--; // 右边界向内收缩
            if (right < left) break; // 判断边界是否相遇

            for(int i=right; i>=left; i--) // 从右到左打印一行
                res[index++] = matrix[bottom][i];
            bottom--; // 下边界向内收缩
            if (bottom < top) break; // 判断边界是否相遇

            for(int i=bottom; i>=top; i--) // 从下到上打印一列
                res[index++] = matrix[i][left];
            left++; // 左边界向内收缩
            if (left > right) break; // 判断边界是否相遇
        }
        return res;
    }
}