LeetCode 48. Rotate Image

建议记住口诀:

顺时针
先转置(斜右下对角线)再翻转(左右翻转)
逆时针
先转置(斜左下对角线)再翻转(左右翻转)

时间复杂度: O ( N ) O(N) O(N) 空间复杂度: O ( N ) O(N) O(N)

JAVA

① 转置加翻转(顺时针)

class Solution {
    public void rotate(int[][] matrix) {
        int len = matrix.length;        // 获取的是第一维数组的长度

        // 转置(斜右下对角线)
        for (int i = 0; i < len; ++i)
            for (int j = i; j < len; ++j) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }

        // 翻转(左右翻转)
        for (int i = 0; i < len; ++i)
            for (int j = 0; j < len / 2; ++j) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][len - j - 1];
                matrix[i][len - j - 1] = tmp;
            }
    }
}

先转置(斜右下对角线)再翻转(左右翻转)

② 转置加翻转(逆时针)

class Solution {
    public void rotate(int[][] matrix) {
        int len = matrix.length;        // 获取的是第一维数组的长度

        // 转置(斜右下对角线)
        for (int i = 0; i < len; ++i)
            for (int j = len-i-1; j >= 0; --j) {			// 改变
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[len-j-1][len-i-1];	// 改变
                matrix[len-j-1][len-i-1] = tmp;				// 改变
            }

        // 翻转(左右翻转)
        for (int i = 0; i < len; ++i)
            for (int j = 0; j < len / 2; ++j) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][len - j - 1];
                matrix[i][len - j - 1] = tmp;
            }
    }
}

先转置(斜左下对角线)再翻转(左右翻转)【或者顺时针三次】

相对于顺时针,转置函数改变的地方用注释写出来了

Python

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        matrix.reverse()				# 翻转(上下翻转)
        for i in range(len(matrix)):	# 转置(斜右下对角线)
            for j in range(i+1,len(matrix)):
                tmp=matrix[i][j]
                matrix[i][j]=matrix[j][i]
                matrix[j][i]=tmp

先翻转(上下翻转)再转置(斜右下对角线)

上一篇:这是一个福利


下一篇:微信小程序背景音乐