受Raymond Chen帖子的启发,假设你有一个4x4二维数组,写一个函数使它旋转90度。Raymond链接到伪代码中的解决方案,但我想看到一些真实的东西。
[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]
就变成:
[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]
更新:Nick的答案是最直接的,但是有没有比n²更好的方法呢?如果矩阵是10000x10000呢?
受Raymond Chen帖子的启发,假设你有一个4x4二维数组,写一个函数使它旋转90度。Raymond链接到伪代码中的解决方案,但我想看到一些真实的东西。
[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]
就变成:
[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]
更新:Nick的答案是最直接的,但是有没有比n²更好的方法呢?如果矩阵是10000x10000呢?
当前回答
下面是我的Ruby版本(注意,值显示的不一样,但它仍然按照描述旋转)。
def rotate(matrix)
result = []
4.times { |x|
result[x] = []
4.times { |y|
result[x][y] = matrix[y][3 - x]
}
}
result
end
matrix = []
matrix[0] = [1,2,3,4]
matrix[1] = [5,6,7,8]
matrix[2] = [9,0,1,2]
matrix[3] = [3,4,5,6]
def print_matrix(matrix)
4.times { |y|
4.times { |x|
print "#{matrix[x][y]} "
}
puts ""
}
end
print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))
输出:
1 5 9 3
2 6 0 4
3 7 1 5
4 8 2 6
4 3 2 1
8 7 6 5
2 1 0 9
6 5 4 3
其他回答
时间- O(N),空间- O(1)
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
int last = n - 1 - i;
for (int j = i; j < last; j++) {
int top = matrix[i][j];
matrix[i][j] = matrix[last - j][i];
matrix[last - j][i] = matrix[last][last - j];
matrix[last][last - j] = matrix[j][last];
matrix[j][last] = top;
}
}
}
private static int[][] rotate(int[][] matrix, int n) {
int[][] rotated = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
rotated[i][j] = matrix[n-j-1][i];
}
}
return rotated;
}
这是我对矩阵90度旋转的尝试,这是c中的2步解决方案,首先转置矩阵,然后交换cols。
#define ROWS 5
#define COLS 5
void print_matrix_b(int B[][COLS], int rows, int cols)
{
for (int i = 0; i <= rows; i++) {
for (int j = 0; j <=cols; j++) {
printf("%d ", B[i][j]);
}
printf("\n");
}
}
void swap_columns(int B[][COLS], int l, int r, int rows)
{
int tmp;
for (int i = 0; i <= rows; i++) {
tmp = B[i][l];
B[i][l] = B[i][r];
B[i][r] = tmp;
}
}
void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
int tmp;
// Transpose the matrix first
for (int i = 0; i <= rows; i++) {
for (int j = i; j <=cols; j++) {
tmp = B[i][j];
B[i][j] = B[j][i];
B[j][i] = tmp;
}
}
// Swap the first and last col and continue until
// the middle.
for (int i = 0; i < (cols / 2); i++)
swap_columns(B, i, cols - i, rows);
}
int _tmain(int argc, _TCHAR* argv[])
{
int B[ROWS][COLS] = {
{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}
};
matrix_2d_rotation(B, ROWS - 1, COLS - 1);
print_matrix_b(B, ROWS - 1, COLS -1);
return 0;
}
在python中:
import numpy as np
a = np.array(
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 0, 1, 2],
[3, 4, 5, 6]
]
)
print(a)
print(b[::-1, :].T)
基于社区wiki算法和这个转置数组的SO答案,这里是一个Swift 4版本,可以逆时针旋转一些2D数组90度。这里假设matrix是一个2D数组:
func rotate(matrix: [[Int]]) -> [[Int]] {
let transposedPoints = transpose(input: matrix)
let rotatedPoints = transposedPoints.map{ Array($0.reversed()) }
return rotatedPoints
}
fileprivate func transpose<T>(input: [[T]]) -> [[T]] {
if input.isEmpty { return [[T]]() }
let count = input[0].count
var out = [[T]](repeating: [T](), count: count)
for outer in input {
for (index, inner) in outer.enumerated() {
out[index].append(inner)
}
}
return out
}