面试题29. 顺时针打印矩阵

面试题29.顺时针打印矩阵

题目描述

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

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

分析

示例1：

i/j	j = 0	j = 1	j = 2
i = 0	1	2	3
i = 1	4	5	6
i = 2	7	8	9
i = 2	10	11	13

示例2：

i/j	j = 0	j = 1	j = 2	j = 3
i = 0	1	2	3	4
i = 1	5	6	7	8
i = 2	9	10	11	12
i = 2	13	14	15	16

可以看一下结果，题目说是顺时针打印，可以想象一下 i 跟 j 的变化

• 循环遍历
• 结束条件是： 当结果数组的长度 == matrix数组的高 * 宽， 即所有子集都遍历过了
• 再来分析一下边界问题, 分析一下 i, j 的变化， 这里以 示例2 为例子
  1. 开始： 向右走， 那么 j++，i不变， 到 j == 3的时候向下， 所以这里要考虑右边的边界问题
  2. 向下走： 那么 i++, j 不变，到 i == 3的时候向左， 所以考虑下边界问题
  3. 向左走： 那么 j--, i 不变，到 j == 0的时候向上，所以考虑左边界问题
  4. 向上走： 那么 i--, j 不变，到 i == 1的时候再一次重复， 1,2,3,4这四步， 但这里要考虑上边界的问题

我这里用 direction 表示方向， 1 => 向右， 2 => 向下， 3 => 向左， 4 =》 向上

这时候就是想什么时候得到边界，在边界的时候改变方向，所以有

• 先设置边界 left = 0, right = colums - 1, up = 0, down = rows - 1, 这里表示左右上下的边界，我们只要操作这个边界就可以了
  另外rows表示有多少行，colums表示有多少列

• i == up && j == left, 我们可以看 i == 0, j == 0的时候，这时候就是向右走

• i == up && j == right, 这时候就是 i == 0， j == 3的时候，那么我们就改变方向，向下走

• i == down && j == right, 这时候就是 i == 3, j == 3，那么又改变方向，向左走

• i == down && j == left, 这时候就是 i == 3, j == 0, 又改变方向，向上走

• 注意： 此时向上走之后，等 i == up + 1 && j == left, 即 i == 1, j ==0, 即5这个地方，那么就向右走，同时，更改边界, left++, right--, up++, down-- 再重复上面的事情

整个过程是：

• 1 => 2 => 3 => 4 => 8 => 12 => 16 => 15 => 14 => 13 => 9 => 5 这是一圈
• 6 => 7 => 11 => 10 这又是一圈

当输入的matrix = [[1],[2],[3]]就只有一列的时候， 另外看示例1, 走完外圈，剩下内圈，只剩下5,8这两个元素的时候也向下走，所以总结 left == right的时候，direction = 2, i++

代码

var spiralOrder = function(matrix) {
    let rows = matrix.length;
    let result = [];
    if(rows == 0) {
        return result
    }
    let columns = matrix[0].length;
    let count = 0;
    let i = 0;
    let j = 0;
    let direction = 1;  // 1 => 向右 2 => 向下 3=> 向左 4 => 向上
    let left = 0;        // 左边界
    let right = columns - 1;  // 右边界
    let up = 0; 
    let down =  rows - 1;

    while(count < rows * columns) {
        const current = matrix[i][j];
        result.push(current);
        count++;
        if(left == right) {  // 当剩下的元素只有一列的时候，只能向下走了
            direction = 2;
            i++;
            continue;
        }
        if(i == up && j == left) {   // 拐点向右
            direction = 1
        } else if(i == up && j == right) {  // 拐点向下
            direction = 2
        } else if(i == down && j == right) { // 拐点向左
            direction = 3;
        } else if(i == down && j == left) { // 拐点向上
            direction = 4
        }

        if(i == up + 1 && j == left) {
            // 完成一圈后，重设定边界
            left = left + 1;
            right = right - 1;
            up = up + 1;
            down = down - 1;
            direction = 1;
        }

        // 根据方向，改变i, j的值
        if(direction == 1) {
            j++;
        } else if(direction == 2) {
            i++;
        } else if(direction == 3) {
            j--;
        } else {
            i--;
        }
    }
    return result
};