当前位置：网站首页>[数组]BM99 顺时针旋转矩阵-简单

[数组]BM99 顺时针旋转矩阵-简单

2022-06-27 18:20:00 【51CTO】

BM99 顺时针旋转矩阵

知识点数组基础数学

描述

有一个nxn整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。

给定一个nxn的矩阵，和矩阵的阶数n,请返回旋转后的nxn矩阵。

数据范围： [数组]BM99 顺时针旋转矩阵-简单_矩阵反转，矩阵中的值满足 [数组]BM99 顺时针旋转矩阵-简单_矩阵反转_02

要求：空间复杂度 [数组]BM99 顺时针旋转矩阵-简单_矩阵反转_03 ，时间复杂度进阶：空间复杂度 [数组]BM99 顺时针旋转矩阵-简单_矩阵反转_05 ，时间复杂度

示例1

输入：

      
      
       
       [[1,2,3],[4,5,6],[7,8,9]],3
      
      
      
      
       
       1.

复制返回值：

      
      
       
       [[7,4,1],[8,5,2],[9,6,3]]
      
      
      
      
       
       1.

题解

按层旋转

思路：

对于一个N阶矩阵的旋转，我们可以通过先旋转一个N-1矩阵，然后再对最外围的一圈进行旋转后得到。因此，题目实际上就是要实现一个算法，将任意阶矩阵的最外围进行旋转。要旋转最外围的一圈，我们可以分别将(0,1),(0,2)...(0,n-1)这些点进行旋转完成，每一步的旋转，只需要进行3次数据交换，假设矩阵阶数是N，则对任意的i >=0且i<=n-1的点(0,i)进行旋转，其交换顺序如下：

swap(mat[0][i],mat[i][n-1])
swap(mat[0][i],mat[n-1][n-i-1])
swap(mat[0][i],mat[n-i-1][0])

代码如下：

       
       #include <bits/stdc++.h>
       
       using 
       
       namespace 
       
       std;
       
       struct 
       
       point
       
{
       
       int 
       
       x;
       
       int 
       
       y;
       
       point() 
       
       = 
       
       default;
       
       point(
       
       const 
       
       point 
       
       &
       
       p) : 
       
       x(
       
       p.
       
       x), 
       
       y(
       
       p.
       
       y) {}
       
       point(
       
       int 
       
       x, 
       
       int 
       
       y) : 
       
       x(
       
       x), 
       
       y(
       
       y) {}
       
};
       
       void 
       
       rotate_level(
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       &
       
       mat, 
       
       point 
       
       left, 
       
       point 
       
       right)
       
{
       
       for (
       
       int 
       
       i 
       
       = 
       
       left.
       
       x; 
       
       i 
       
       <= 
       
       right.
       
       x 
       
       - 
       
       1; 
       
       ++
       
       i)
       
  {
       
       std::swap(
       
       mat[
       
       left.
       
       y][
       
       i], 
       
       mat[
       
       left.
       
       y 
       
       + (
       
       i 
       
       - 
       
       left.
       
       x)][
       
       right.
       
       x]);
       
       std::swap(
       
       mat[
       
       left.
       
       y][
       
       i], 
       
       mat[
       
       right.
       
       y][
       
       right.
       
       x 
       
       - (
       
       i 
       
       - 
       
       left.
       
       x)]);
       
       std::swap(
       
       mat[
       
       left.
       
       y][
       
       i], 
       
       mat[
       
       right.
       
       y 
       
       - (
       
       i 
       
       - 
       
       left.
       
       x)][
       
       left.
       
       x]);
       
  }
       
}
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       rotateMatrix(
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       mat, 
       
       int 
       
       n)
       
{
       
       point 
       
       left(
       
       0, 
       
       0);
       
       point 
       
       right(
       
       n 
       
       - 
       
       1, 
       
       n 
       
       - 
       
       1);
       
       while (
       
       left.
       
       x 
       
       < 
       
       right.
       
       x)
       
  {
       
       rotate_level(
       
       mat, 
       
       left, 
       
       right);
       
       left.
       
       x 
       
       += 
       
       1;
       
       left.
       
       y 
       
       += 
       
       1;
       
       right.
       
       x 
       
       -= 
       
       1;
       
       right.
       
       y 
       
       -= 
       
       1;
       
  }
       
       return 
       
       mat;
       
}
      
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.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.

根据矩阵的特性，先交换上下矩阵，然后再对每行进行反转

步骤：

交换上下矩阵
对每行进行反转

代码如下：

       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       rotateMatrix(
       
       vector
       
       <
       
       vector
       
       <
       
       int
       
       >> 
       
       mat, 
       
       int 
       
       n)
       
{
       
       //矩阵转置
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       n; 
       
       i
       
       ++)
       
  {
       
       for (
       
       int 
       
       j 
       
       = 
       
       0; 
       
       j 
       
       < 
       
       i; 
       
       j
       
       ++)
       
    {
       
       swap(
       
       mat[
       
       i][
       
       j], 
       
       mat[
       
       j][
       
       i]); 
       
       //交换上三角与下三角对应的元素
       
    }
       
  }
       
       //每行翻转
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       n; 
       
       i
       
       ++)
       
  {
       
       reverse(
       
       mat[
       
       i].
       
       begin(), 
       
       mat[
       
       i].
       
       end());
       
  }
       
       return 
       
       mat;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.