Rotate Image (M)
題目
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOTallocate another 2D matrix and do the rotation.
Example 1:
Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Example 2:
Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
題意
將給定的矩陣順時針旋轉90°，要求只能在原矩陣上進行修改，
思路
比較直接的方法是模擬旋轉，如下圖，經過旋轉后，第一列變為第一行，第二列變為第二行……而第一行變為最后一列，第二行變為最后第二列……由此可以得到旋轉規律：\((i,\ j) \rightarrow (j,\ n-i-1) \rightarrow (n-i-1,\ n-j-1) \rightarrow (n-j-1,\ i) \rightarrow (i,\ j)\)，
為了不重復操作，只將下圖中的區域①旋轉3次得到區域②、③、④，
另一種比較取巧的方法是，如下圖，先沿著中心水平線上下翻轉，再沿著左上到右下的主對角線翻轉，就完成了順時針旋轉90°，
代碼實作
Java
旋轉法
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
for (int j = i; j < n - i - 1; j++) {
int temp = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = matrix[i][j];
matrix[i][j] = temp;
}
}
}
}
翻轉法
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// 上下翻轉
for (int i = 0; i < n / 2; i++) {
for (int j = 0; j < n; j++) {
swap(matrix, i, j, n - 1 - i, j);
}
}
// 主對角線翻轉
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
swap(matrix, i, j, j, i);
}
}
}
private void swap(int[][] matrix, int i, int j, int x, int y) {
int temp = matrix[i][j];
matrix[i][j] = matrix[x][y];
matrix[x][y] = temp;
}
}
JavaScript
旋轉法
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var rotate = function (matrix) {
let n = matrix.length
for (let i = 0; i < Math.trunc(n / 2); i++) {
for (let j = i; j <= n - 1 - i; j++) {
let tmp = matrix[i][j]
matrix[i][j] = matrix[n - 1 - j][i]
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
matrix[j][n - 1 - i] = tmp
}
}
}
翻轉法
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var rotate = function (matrix) {
let n = matrix.length
for (let i = 0; i < Math.trunc(n / 2); i++) {
for (let j = 0; j < n; j++) {
[matrix[i][j], matrix[n - 1 - i][j]] = [matrix[n - 1 - i][j], matrix[i][j]]
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]]
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/33845.html
標籤：其他