转圈打印矩阵.md

转圈打印矩阵

题目

给定一个整型矩阵matrix，请按照转圈的方式打印它，要求额外空间复杂度为O(1)。

例如
1   2   3   4   5
6   7   8   9   10
11  12  13  14  15
16  17  18  19  20

打印结果为: 1 2 3 4 5 10 15 20 19 18 17 16 11 6 7 8 9 14 13 12

思路

先打印外圈 1 2 3 4 5 10 15 20 19 18 17 16 11 6
再打印内圈 7 8 9 14 13 12
...
核心在于确定每一圈的左上角和右下角的坐标

代码

PHP

class CircleMatrixPrint
{
    public static function circleMatrix($matrix)
    {
        // 左上角横坐标
        $leftX = 0;
        // 左上角纵坐标
        $leftY = 0;
        // 右下角横坐标
        $rightX = count($matrix) - 1;
        // 右下角纵坐标
        $rightY = count($matrix[0]) - 1;

        // 边界条件
        while ($leftX <= $rightX && $leftY <= $rightY) {
            // 打印完一圈, 左上角的点向右下移动, 右下角的点向左上移动
            self::printEdge($matrix, $leftX++, $leftY++, $rightX--, $rightY--);
        }
    }

    public static function printEdge($matrix, $leftX, $leftY, $rightX, $rightY)
    {
        // 只有一行
        if ($leftX == $rightX) {
            for ($i = $leftY; $i <= $rightY; $i++) {
                echo $matrix[$leftX][$i] . ' ';
            }
        }
        // 只有一列
        else if ($leftY == $rightY) {
            for ($i = $leftX; $i <= $rightX; $i++) {
                echo $matrix[$i][$leftY] . ' ';
            }
        }
        // 普通矩形
        else {
            $currX = $leftX;
            $currY = $leftY;

            // 打印矩形top
            while ($currY != $rightY) {
                echo $matrix[$currX][$currY] . ' ';
                $currY++;
            }

            // 打印矩形right
            while ($currX != $rightX) {
                echo $matrix[$currX][$currY] . ' ';
                $currX++;
            }

            // 打印矩形bottom
            while ($currY != $leftX) {
                echo $matrix[$currX][$currY] . ' ';
                $currY--;
            }

            // 打印矩形left
            while ($currX != $leftX) {
                echo $matrix[$currX][$currY] . ' ';
                $currX--;
            }
        }
    }
}

// Test
$matrix = [
    [ 1, 2, 3, 4, 5 ],
    [ 6, 7, 8, 9, 10 ],
    [ 11, 12, 13, 14, 15 ],
    [ 16, 17, 18, 19, 20 ]
];
CircleMatrixPrint::circleMatrix($matrix);

JAVA

public class CircleMatrixPrint {
	public static void circleMatrixPrint(int[][] matrix) {
		// 左上角横坐标
		int leftX = 0;
		// 左上角纵坐标
		int leftY = 0;
		// 右下角横坐标 
		int rightX = matrix.length - 1;
		// 右下角纵坐标
		int rightY = matrix[0].length - 1;
		
		// 边界条件
		while (leftX <= rightX && leftY <= rightY) {
			// 打印完一圈, 左上角的点向右下移动, 右下角的点向左上移动
			printEdge(matrix, leftX++, leftY++, rightX--, rightY--);
		}
	}
	
	public static void printEdge(int[][] matrix, int leftX, int leftY, int rightX, int rightY) {
		// 只有一行
		if (leftX == rightX) {
			for (int i = leftY; i <= rightY; i++) {
				System.out.println(matrix[leftX][i] + " ");
			}
		} 
		// 只有一列
		else if (leftY == rightY) {
			for (int i = leftY; i <= rightY; i++) {
				System.out.println(matrix[i][leftY] + " ");
			}
		}
		// 普通矩形
		else {
			int currX = leftX;
			int currY = leftY;
			
			// 打印矩形top
			while (currY != rightY) {
				System.out.println(matrix[currX][currY] + " ");
				currY++;
			}
			
			// 打印矩形right
			while (currX != rightX) {
				System.out.println(matrix[currX][currY]+ " ");
				currX++;
			}
			
			// 打印矩形bottom
			while (currY != leftY) {
				System.out.println(matrix[currX][currY]+ " ");
				currY--;
			}
			
			// 打印矩形left
			while (currX != leftX) {
				System.out.println(matrix[currX][currY]+ " ");
				currX--;
			}
		}
	}
	
	public static void main(String[] args) {
		int[][] matrix = { 
			{ 1, 2, 3, 4, 5 }, 
			{ 6, 7, 8, 9, 10 }, 
			{ 11, 12, 13, 14, 15 },
			{ 16, 17, 18, 19, 20 } 
		};
		
		circleMatrixPrint(matrix);
	}
}