受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呢?
当前回答
原地旋转不可能比O(n²)更快，原因是如果我们想旋转矩阵，我们必须至少一次触及所有n²元素，无论你实现什么算法。
其他回答
哦，伙计。我一直认为这是一个“我很无聊，我能思考什么”的谜题。我想出了我的原地换位码，但到了这里发现你的和我的几乎一模一样……啊,好。这里是Ruby版本。
require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }
pp a
0.upto(n/2-1) do |i|
i.upto(n-i-2) do |j|
tmp = a[i][j]
a[i][j] = a[n-j-1][i]
a[n-j-1][i] = a[n-i-1][n-j-1]
a[n-i-1][n-j-1] = a[j][n-i-1]
a[j][n-i-1] = tmp
end
end
pp a
下面是一个原地旋转的数组，而不是使用一个全新的数组来保存结果。我已经停止了数组的初始化和输出。这只适用于正方形数组，但它们可以是任何大小。内存开销等于数组中一个元素的大小，因此您可以对任意大的数组进行旋转。
int a[4][4];
int n = 4;
int tmp;
for (int i = 0; i < n / 2; i++)
{
for (int j = i; j < n - i - 1; j++)
{
tmp = a[i][j];
a[i][j] = a[j][n-i-1];
a[j][n-i-1] = a[n-i-1][n-j-1];
a[n-i-1][n-j-1] = a[n-j-1][i];
a[n-j-1][i] = tmp;
}
}
在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)
在Eigen (c++)中:
Eigen::Matrix2d mat;
mat << 1, 2,
3, 4;
std::cout << mat << "\n\n";
Eigen::Matrix2d r_plus_90 = mat.transpose().rowwise().reverse();
std::cout << r_plus_90 << "\n\n";
Eigen::Matrix2d r_minus_90 = mat.transpose().colwise().reverse();
std::cout << r_minus_90 << "\n\n";
Eigen::Matrix2d r_180 = mat.colwise().reverse().rowwise().reverse(); // +180 same as -180
std::cout << r_180 << "\n\n";
输出:
1 2
3 4
3 1
4 2
2 4
1 3
4 3
2 1
#转置是Ruby的Array类的标准方法，因此:
% irb
irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
irb(main):002:0> m.reverse.transpose
=> [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]
实现是一个用c写的n^2转置函数，你可以在这里看到: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose 通过选择“点击切换源”旁边的“转置”。
我记得比O(n^2)的解更好，但只适用于特殊构造的矩阵(如稀疏矩阵)
