最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

经典面试题25–顺时针打印矩阵

XAMPP相关 admin 32浏览 0评论

来源:LeetCode

难度:中等

描述:

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

 

示例1:

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]
解释:无

示例2:

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]
解释:无

 

分析:

        这个题目怎么说呢…,好理解么?好理解!就是让咱们从外向里以顺时针的方式遍历整个二维数组。难么?不难!恶心么?恶心!!

这里介绍一种一层一层遍历打印的方式,由外至内,层层递进。具体步骤思路如下

 

解题

方法一:由外至内,层层递进法

思路:

将矩阵看成若干层,首先打印最外层的元素,其次打印次外层的元素,直到打印最内层的元素。咱们定义四个坐标:(top, left)、(top, right)、(bottom, left)、(bottom, right)。

  • 对于每一层,先从左上方(top, left)从左到右遍历到(top, right)
  • 然后在(top + 1, right)从上到下遍历到(bottom,right)
  • 之后在(bottom, right – 1)从右往左遍历到(bottom,left + 1)
  • 最后在(bottom, left)从下往上遍历到(top +1, left)

遍历完当前层的元素之后,将left 和 top 分别增加 1,将 right 和 bottom 分别减少 1,进入下一层继续遍历,直到遍历完所有元素为止

 

代码:

 1public int[] spiralOrder(int[][] matrix) {
 2    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
 3        return new int[0];
 4    }
 5    int rows = matrix.length;
 6    int columns = matrix[0].length;
 7    //rows * columns 等于二维数组个数
 8    int[] order = new int[rows * columns];
 9    int index = 0;
10    //左右
11    int left = 0, right = columns - 1;
12    //上下
13    int top = 0, bottom = rows - 1;
14    while (left <= right && top <= bottom) {
15        //先打印外层最上面那一层
16        for (int column = left; column <= right; column++) {
17            order[index++] = matrix[top][column];
18        }
19        //再打印最右边那一层
20        for (int row = top + 1; row <= bottom; row++) {
21            order[index++] = matrix[row][right];
22        }
23        if (left < right && top < bottom) {
24            //打印底下那一层
25            for (int column = right - 1; column > left; column--) {
26                order[index++] = matrix[bottom][column];
27            }
28            //打印左边那一层
29            for (int row = bottom; row > top; row--) {
30                order[index++] = matrix[row][left];
31            }
32        }
33        //外面一层打印完毕,往里面递进一层
34        left++;
35        right--;
36        top++;
37        bottom--;
38    }
39    return order;
40}

时间复杂度:O(m * n)  m和n 分别对应二维数组的行和列

空间复杂度:O(n) 

 

以上仅是个人思路解法

转载请注明:XAMPP中文组官网 » 经典面试题25–顺时针打印矩阵