Jamzen的技术博客
0%

LeetCode.旋转图像

发表于 分类于 Valine：

给定一个n×n的二维矩阵表示一个图像。将图像顺时针旋转90度。说明：你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

  • 示例1:
    给定 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]
    ]

解法：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
object RotateArray {

     def main(args: Array[String]): Unit = {

          val arr0 = Array[Array[Int]](
               Array[Int](1, 2),
               Array[Int](3, 4)
          )
          rotate(arr0)
          for (elem <- arr0) {
               println(java.util.Arrays.toString(elem))
          }

          val arr = Array[Array[Int]](
               Array[Int](1, 2, 3),
               Array[Int](4, 5, 6),
               Array[Int](7, 8, 9)
          )
          rotate(arr)
          for (elem <- arr) {
               println(java.util.Arrays.toString(elem))
          }

          println("-------------------------------------------")
          val arr1 = Array[Array[Int]](
               Array[Int](1, 2, 3, 4),
               Array[Int](5, 6, 7, 8),
               Array[Int](9, 10, 11, 12),
               Array[Int](13, 14, 15, 16)
          )
          rotate(arr1)
          for (elem <- arr1) {
               println(java.util.Arrays.toString(elem))
          }

          println("-------------------------------------------")
          val arr2 = Array[Array[Int]](
               Array[Int](1, 2, 3, 4, 5, 6),
               Array[Int](7, 8, 9, 10, 11, 12),
               Array[Int](13, 14, 15, 16, 17, 18),
               Array[Int](19, 20, 21, 22, 23, 24),
               Array[Int](25, 26, 27, 28, 29, 30),
               Array[Int](31, 32, 33, 34, 35, 36)
          )
          rotate(arr2)
          for (elem <- arr2) {
               println(java.util.Arrays.toString(elem))
          }

          println("-------------------------------------------")
          val arr3 = Array[Array[Int]](
               Array[Int](5, 1, 9, 11),
               Array[Int](2, 4, 8, 10),
               Array[Int](13, 3, 6, 7),
               Array[Int](15, 14, 12, 16)
          )
          rotate(arr3)
          for (elem <- arr3) {
               println(java.util.Arrays.toString(elem))
          }
     }

     /**
      * 先上下翻转，后转置，时间复杂度O(n^2)
      **/
     def rotate(matrix: Array[Array[Int]]): Unit = {
          for (i <- 0 until matrix.length / 2) {
               for (j <- 0 until matrix.length) {
                    val tmp = matrix(i)(j)
                    matrix(i)(j) = matrix(matrix.length - 1 - i)(j)
                    matrix(matrix.length - 1 - i)(j) = tmp
               }
          }

          for (i <- 0 until matrix.length) {
               for (j <- i + 1 until matrix.length) {
                    val tmp = matrix(i)(j)
                    matrix(i)(j) = matrix(j)(i)
                    matrix(j)(i) = tmp
               }
          }
     }

     /**
      * 由内向外，每次旋转一圈，时间复杂度O(n^2)
      **/
     def rotate2(matrix: Array[Array[Int]]): Unit = {
          var tmp = 0
          val flag = (matrix.length % 2 == 0)
          for (i <- matrix.length / 2 - 1 to 0 by -1) {
               val len = (matrix.length / 2 - i) * 2 + (if (flag) 0 else 1)
               for (j <- i until i + len - 1) {
                    val start = (i, j)
                    val topRight = (j, i + len - 1)
                    val lowRight = (i + len - 1, i + len - 1 - (j - i))
                    val lowLeft = (i + len - 1 - (j - i), i)

                    //println(start, topRight, lowRight, lowLeft)

                    tmp = matrix(topRight._1)(topRight._2)
                    matrix(topRight._1)(topRight._2) = matrix(start._1)(start._2)
                    matrix(start._1)(start._2) = matrix(lowRight._1)(lowRight._2)
                    matrix(lowRight._1)(lowRight._2) = tmp

                    tmp = matrix(start._1)(start._2)
                    matrix(start._1)(start._2) = matrix(lowLeft._1)(lowLeft._2)
                    matrix(lowLeft._1)(lowLeft._2) = tmp
               }
          }
     }
}