力扣00048.旋转图像

发表于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 6 分钟
旋转图像、数组、数学、矩阵、中等

题目描述

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

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

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        for (int i = 0; i < n; ++i) {
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

结果

执行用时 : 0 ms, 击败 100.00% 使用 C++ 的用户

内存消耗 : 8.52 MB, 击败 12.36% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Java 的用户

内存消耗 : 41.23 MB, 击败 14.96% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for i in range(n):
            matrix[i].reverse()

结果

执行用时 : 18 ms, 击败 39.91% 使用 Python 的用户

内存消耗 : 11.35 MB, 击败 98.01% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for i in range(n):
            matrix[i].reverse()

结果

执行用时 : 35 ms, 击败 85.58% 使用 Python3 的用户

内存消耗 : 16.36 MB, 击败 46.87% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void rotate(int** matrix, int matrixSize, int* matrixColSize) {
    int n = matrixSize;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n / 2; ++j) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[i][n - 1 - j];
            matrix[i][n - 1 - j] = temp;
        }
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 C 的用户

内存消耗 : 6.14 MB, 击败 84.61% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public void Rotate(int[][] matrix) {
        int n = matrix.Length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            Array.Reverse(matrix[i]);
        }
    }
}

结果

执行用时 : 104 ms, 击败 73.95% 使用 C# 的用户

内存消耗 : 45.74 MB, 击败 6.72% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    const n = matrix.length;
    for (let i = 0; i < n; ++i) {
        for (let j = i + 1; j < n; ++j) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }
    for (let i = 0; i < n; ++i) {
        matrix[i].reverse();
    }
};

结果

执行用时 : 50 ms, 击败 94.94% 使用 JavaScript 的用户

内存消耗 : 49.44 MB, 击败 13.07% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 Do not return anything, modify matrix in-place instead.
 */
function rotate(matrix: number[][]): void {
    const n: number = matrix.length;
    for (let i = 0; i < n; ++i) {
        for (let j = i + 1; j < n; ++j) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }
    for (let i = 0; i < n; ++i) {
        matrix[i].reverse();
    }
}

结果

执行用时 : 47 ms, 击败 100.00% 使用 TypeScript 的用户

内存消耗 : 51.76 MB, 击败 7.02% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    
    /**
     * @param Integer[][] $matrix
     * @return NULL
     */
    function rotate(&$matrix) {
        $n = count($matrix);
        for ($i = 0; $i < $n; ++$i) {
            for ($j = $i + 1; $j < $n; ++$j) {
                [$matrix[$i][$j], $matrix[$j][$i]] = [$matrix[$j][$i], $matrix[$i][$j]];
            }
        }
        for ($i = 0; $i < $n; ++$i) {
            $matrix[$i] = array_reverse($matrix[$i]);
        }
    }
}

结果

执行用时 : 9 ms, 击败 25.00% 使用 PHP 的用户

内存消耗 : 20.14 MB, 击败 5.00% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    func rotate(_ matrix: inout [[Int]]) {
        let n = matrix.count
        for i in 0..<n {
            for j in i+1..<n {
                (matrix[i][j], matrix[j][i]) = (matrix[j][i], matrix[i][j])
            }
        }
        for i in 0..<n {
            matrix[i].reverse()
        }
    }
}

结果

执行用时 : 6 ms, 击败 78.82% 使用 Swift 的用户

内存消耗 : 15.69 MB, 击败 5.88% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    fun rotate(matrix: Array<IntArray>): Unit {
        val n = matrix.size
        for (i in 0 until n) {
            for (j in i + 1 until n) {
                matrix[i][j] = matrix[j][i].also { matrix[j][i] = matrix[i][j] }
            }
        }
        for (i in 0 until n) {
            matrix[i].reverse()
        }
    }
}

结果

执行用时 : 206 ms, 击败 8.33% 使用 Kotlin 的用户

内存消耗 : 37.55 MB, 击败 6.25% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
  void rotate(List<List<int>> matrix) {
    final n = matrix.length;
    for (var i = 0; i < n; ++i) {
      for (var j = i + 1; j < n; ++j) {
        final temp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = temp;
      }
    }
    for (var i = 0; i < n; ++i) {
      matrix[i] = List<int>.from(matrix[i].reversed);
    }
  }
}

结果

执行用时 : 299 ms, 击败 -% 使用 Dart 的用户

内存消耗 : 144.31 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
func rotate(matrix [][]int) {
    n := len(matrix)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }
    for i := 0; i < n; i++ {
        for j, k := 0, n-1; j < k; j, k = j+1, k-1 {
            matrix[i][j], matrix[i][k] = matrix[i][k], matrix[i][j]
        }
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Go 的用户

内存消耗 : 2.11 MB, 击败 16.92% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
# @param {Integer[][]} matrix
# @return {Void} Do not return anything, modify matrix in-place instead.
def rotate(matrix)
  n = matrix.length
  (0...n).each do |i|
    (i + 1...n).each do |j|
      matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    end
  end
  matrix.each { |row| row.reverse! }
end

结果

执行用时 : 41 ms, 击败 100.00% 使用 Ruby 的用户

内存消耗 : 206.51 MB, 击败 50.00% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
object Solution {
  def rotate(matrix: Array[Array[Int]]): Unit = {
    val n = matrix.length
    for (i <- 0 until n) {
      for (j <- i + 1 until n) {
        val temp = matrix(i)(j)
        matrix(i)(j) = matrix(j)(i)
        matrix(j)(i) = temp
      }
    }
    for (i <- 0 until n) {
      matrix(i) = matrix(i).reverse
    }
  }
  def main(args: Array[String]): Unit = {
    val matrix = Array(
      Array(1, 2, 3),
      Array(4, 5, 6),
      Array(7, 8, 9)
    )
    rotate(matrix)
    for (row <- matrix) {
      println(row.mkString(", "))
    }
  }
}

结果

执行用时 : 464 ms, 击败 88.89% 使用 Scala 的用户

内存消耗 : 54.36 MB, 击败 22.22% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
impl Solution {
    pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
        let n = matrix.len();
        for i in 0..n {
            for j in i + 1..n {
                let temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        for row in matrix.iter_mut() {
            row.reverse();
        }
    }
}

结果

执行用时 : 0 ms, 击败 100.00% 使用 Rust 的用户

内存消耗 : 2.23 MB, 击败 16.67% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户