algorithm - 假设矩阵空间为 max(M,N)*max(M,N) 是否有顺时针旋转 M*N 二维矩阵的好方法

Question

感谢任何建议。搜索互联网但没有运气假设原始矩阵有足够大的尺寸用于原地旋转

{{1,2},{3,4},{5,6}} 到 {{5,3,1},{6,4,2}}

或

1 2

3 4

5 6

顺时针旋转到

5 3 1

6 4 2

谢谢。

Answer 1

一种简单的方法是将矩阵左右翻转或上下翻转(可以通过单个列或行的 in-place reversing 轻松完成)和就地矩阵转置相结合，请参阅 mcdowella 的 link 。例如，请参见 Numpy 的 source code 函数的 rot90，它正是执行这两个步骤(swapaxis 基本上是一个转置)。

您可以一步完成所有操作，但这可能需要以某种螺旋模式遍历矩阵。这将花费相当大的努力才能正确实现，并且考虑到用于交换和转置的高效算法(例如针对缓存访问优化)的可用性，这甚至可能更慢。