旋转正方形矩阵.md

旋转正方形矩阵

题目

给定一个整型正方形矩阵matrix，请把该矩阵调整成顺时针旋转90度的样子，要求额外空间复杂度为O(1)。

例如
1  2  3                      7  4  1      
4  5  6         ------->     8  5  2
7  8  9                      9  6  3

思路

先转外圈，后转内圈

外圈:
1  3  9  7四个点相互交换位置。  7来到1的位置、9来到7的位置、3来到9的位置、1来到3的位置
2  6  8  4四个点相互交换位置。  4来到2的位置、8来到4的位置、6来到8的位置、2来到6的位置

代码

PHP

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

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

    public static function rotateEdge(&$matrix, $leftX, $leftY, $rightX, $rightY)
    {
        $times = $rightX - $leftX;
        $tmp = 0;
        for ($i = 0; $i < $times; $i++) {
            $tmp = $matrix[$leftX][$leftY + $i];
            // 正方形top
            $matrix[$leftX][$leftY + $i] = $matrix[$rightX - $i][$leftY];

            // 正方形left
            $matrix[$rightX - $i][$leftY] = $matrix[$rightX][$rightY - $i];

            // 正方形bottom
            $matrix[$rightX][$rightY - $i] = $matrix[$leftX + $i][$rightY];

            // 正方形right
            $matrix[$leftX + $i][$rightY] = $tmp;
        }
    }

    // 打印正方形
    public static function printMatrix($matrix)
    {
        $len = count($matrix);
        for ($i = 0; $i < $len; $i++) {
            for ($j = 0; $j < $len; $j++) {
                echo $matrix[$i][$j] . ' ';
            }
            echo PHP_EOL;
        }
    }
}

// Test
$matrix = [
    [ 1, 2, 3, 4 ],
    [ 5, 6, 7, 8 ],
    [ 9, 10, 11, 12 ],
    [ 13, 14, 15, 16 ]
];
RotateMatrix::rotate($matrix);
RotateMatrix::printMatrix($matrix);

JAVA

public class RotateMatrix {
	public static void rotate(int[][] matrix) {
		// 左上角横坐标
		int leftX = 0;
		// 左上角纵坐标
		int leftY = leftX;
		// 右下角横坐标 
		int rightX = matrix.length - 1;
		// 右下角纵坐标
		int rightY = rightX;
		
		// 边界条件
		while (leftX <= rightX) {
			// 左上角的点向右下移动, 右下角的点向左上移动, 转为内圈
			rotateEdge(matrix, leftX++, leftY++, rightX--, rightY--);
		}
	}
	
	public static void rotateEdge(int[][] matrix, int leftX, int leftY, int rightX, int rightY) {
		int times = rightX - leftX;
		int tmp = 0;
		for (int i = 0; i < times; i++) {
			tmp = matrix[leftX][leftY + i];
			// 正方形top
			matrix[leftX][leftY + i] = matrix[rightX - i][leftY];
			// 正方形left
			matrix[rightX - i][leftY] = matrix[rightX][rightY - i];
			// 正方形bottom
			matrix[rightX][rightY - i] = matrix[leftX + i][rightY];
			// 正方形right
			matrix[leftX + i][rightY] = tmp;
		}
	}
	
	// 打印正方形
	public static void printMatrix(int[][] matrix) {
		for (int i = 0; i != matrix.length; i++) {
			for (int j = 0; j != matrix[0].length; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		int[][] matrix = { 
			{ 1, 2, 3, 4 }, 
			{ 5, 6, 7, 8 }, 
			{ 9, 10, 11, 12 },
			{ 13, 14, 15, 16 } 
		};
		
		rotate(matrix);
		printMatrix(matrix);
	}
}

执行结果

13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4

参考

• https://blog.csdn.net/itcats_cn/article/details/83786226