旋转矩阵

难度:

标签:

题目描述

Given an image represented by an N x N matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

Example 1:

Given matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

Rotate the matrix in place. It becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Example 2:

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

Rotate the matrix in place. It becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

代码结果

运行时间: 19 ms, 内存: 16.0 MB

// Solution for rotating an N x N matrix 90 degrees clockwise in Java using Streams
// Note: Java Streams are not typically used for matrix manipulations like this, but we
// can use them to simplify the code for reading or displaying the matrix.
// The algorithm involves the same two steps as the standard Java solution:
// 1. Transpose the matrix (swap rows with columns)
// 2. Reverse each row
import java.util.Arrays;
import java.util.Collections;
public class RotateImageStream {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // Transpose the matrix
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // Reverse each row using Streams
        for (int i = 0; i < n; i++) {
            Integer[] row = Arrays.stream(matrix[i]).boxed().toArray(Integer[]::new);
            Collections.reverse(Arrays.asList(row));
            matrix[i] = Arrays.stream(row).mapToInt(Integer::intValue).toArray();
        }
    }
}

解释

方法:

该题解采用了一种原地旋转的方法。首先设定循环的层数为 n//2，对于每一层，使用一个嵌套的循环来处理这一层的元素。旋转过程涉及到四个相关联的元素，这四个元素分别位于矩阵的四个不同的‘角’位置。对于每一对(i, j)，进行以下转换： 1. 保存 matrix[i][j] 的值到临时变量 tmp。 2. 将 matrix[n-1-j][i] 的值移动到 matrix[i][j]。 3. 将 matrix[n-1-i][n-1-j] 的值移动到 matrix[n-1-j][i]。 4. 将 matrix[j][n-1-i] 的值移动到 matrix[n-1-i][n-1-j]。 5. 将 tmp (原 matrix[i][j] 的值) 移动到 matrix[j][n-1-i]。这个过程会使得每个元素被旋转到正确的位置，并且只使用一个额外变量，满足原地旋转的要求。

时间复杂度:

O(N^2)

空间复杂度:

O(1)

代码细节讲解

🦆

为什么在旋转矩阵时选择`n//2`作为层数进行循环，这种分层处理的逻辑是什么？

▷

在旋转矩阵时选择`n//2`作为层数进行循环的原因是，对于一个n*n的矩阵，其旋转可以视为从最外层开始逐层向内部进行。每一层都可以看作是一个环形结构，需要整体旋转。由于每次处理一层时都在同时处理该层的上下两边，因此只需要遍历到矩阵中间的层即可。对于奇数n，中间的单个元素不需要移动；对于偶数n，最内层已经是最后的两行两列在之前的层已经处理完毕。因此，`n//2`能够确保所有层都被正确处理。

🦆

在处理每一层的元素时，为什么使用`(n+1)//2`来确定每层的迭代次数？

▷

在处理每一层的元素时，使用`(n+1)//2`来确定每层的迭代次数是为了确保在每一层中的每个元素都被处理到，尤其是当n为奇数时。这是因为在每一层中，我们需要处理从左到右的元素，并且这些元素在旋转后会移动到不同的位置。当矩阵的维度为奇数时，中间的列需要额外的处理以确保中心元素也被旋转到正确的位置。因此，`(n+1)//2`可以保证在所有情况下，每层的元素都被充分旋转。

🦆

在进行原地旋转时，变量`tmp`的使用是否确保了所有元素的正确交换，还是有可能出现某些元素未被正确旋转的情况？

▷

在进行原地旋转时，变量`tmp`的使用确保了所有元素的正确交换。这种方法通过保存一个元素的值到`tmp`，然后依次将其它三个相关联的元素移到正确的位置，最后将保存在`tmp`中的值移到最后一个位置。这个过程形成了一个完整的循环，确保了四个元素都被旋转到了正确的位置。由于每个元素只被处理一次，并且每次处理都包括了所有相关联的四个位置，因此不会出现错过某些元素或未被正确旋转的情况。

旋转矩阵

题目描述

代码结果

解释

代码细节讲解

相关问题