剑指offer-(19)顺时针打印矩阵

题目描述

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下矩阵: 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.

题目分析

首先我们需要把这个复杂的问题分解为简单的问题,打印矩阵也就是一圈一圈的打印出来,所以我们需要解决的问题就是:

1.什么时候该继续打印下一圈即里面那一圈,也就是要找到循环的条件。

2.一圈该如何打印。

那么什么是循环结束的条件呢?也就是我们需要思考从第一圈到第二圈的条件是什么或者说他们有什么共同的特征。我们注意4X4的矩阵,只有两圈,到从第一圈到第二圈,起点从(0,0)变为了(1,1),我们发现4>1*2,类似的对于一个5X5的矩阵而言,最后一圈只有一个数字,起点坐标为(2,2),满足5>2*2,同理对于6X6的矩阵也是类似。故可以得出循环的条件就是columns>startX*2并且rows>startY*2。

然后我们就要实现打印一圈,再分解也就是从左到右,从上到下,从右到左,从下到上。不过要注意下边界条件,也就是最后一圈构成不了一个完整的圈的一些条件,找到了就很好写出代码了。

除此此外,还有一种思路比较巧妙的解法:模拟魔方逆时针解法。

例如 
1 2 3
4 5 6
7 8 9
输出并删除第一行后,再进行一次逆时针旋转,就变成:
6 9
5 8
4 7
继续重复上述操作即可

代码

第一种方法:

// 第一种
function printMatrix(matrix) {
if (matrix === null) return null;
const rows = matrix.length,
cols = matrix[0].length;
let start = 0,
res = [];
while (rows > start * 2 && cols > start * 2) {
res = res.concat(printMatrixInCircle(matrix, rows, cols, start));
start++;
}
return res;
}
function printMatrixInCircle(matrix, rows, cols, start) {
const endX = cols - 1 - start,
endY = rows - 1 - start,
res = [];
for (let i = start; i <= endX; i++) {
res.push(matrix[start][i]);
}
for (let i = start + 1; i <= endY; i++) {
res.push(matrix[i][endX]);
}
for (let i = endX - 1; i >= start && endY > start; i--) {
res.push(matrix[endY][i]);
}
for (let i = endY - 1; i >= start + 1 && endX > start; i--) {
res.push(matrix[i][start]);
}
return res;
}

第二种方法:

// 第二种
function printMatrix2(matrix) {
if (!matrix) return;
let res = [];
const firstRow = matrix.shift();
res = res.concat(firstRow);
while (matrix.length) {
// 判断数组是否为空一定要用matrix.length来判断
matrix = rotateMatrix(matrix);
res = res.concat(matrix.shift());
}
return res;
}
function rotateMatrix(matrix) {
if (matrix[0].length === undefined) return matrix; // 数组为一维数组时,直接返回原数组
const rows = matrix.length,
cols = matrix[0].length,
newMatrix = [];
for (let j = cols - 1; j >= 0; j--) {
const tempMatrix = [];
for (let i = 0; i < rows; i++) {
tempMatrix.push(matrix[i][j]);
}
newMatrix.push(tempMatrix);
}
return newMatrix;
}
上一篇:Spring:笔记整理(1)——HelloWorld


下一篇:dubbo的安装和使用