受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呢?


当前回答

下面是PHP的递归方法:

$m = array();
            $m[0] = array('a', 'b', 'c');
            $m[1] = array('d', 'e', 'f');
            $m[2] = array('g', 'h', 'i');
            $newMatrix = array();

            function rotateMatrix($m, $i = 0, &$newMatrix)
            {
                foreach ($m as $chunk) {
                    $newChunk[] = $chunk[$i];
                }
                $newMatrix[] = array_reverse($newChunk);
                $i++;

                if ($i < count($m)) {
                    rotateMatrix($m, $i, $newMatrix);
                }
            }

            rotateMatrix($m, 0, $newMatrix);
            echo '<pre>';
            var_dump($newMatrix);
            echo '<pre>';

其他回答

从线性的角度来看,考虑以下矩阵:

    1 2 3        0 0 1
A = 4 5 6    B = 0 1 0
    7 8 9        1 0 0

现在求A

     1 4 7
A' = 2 5 8
     3 6 9

考虑A'对B的作用,或B对A'的作用。 分别为:

      7 4 1          3 6 9
A'B = 8 5 2    BA' = 2 5 8
      9 6 3          1 4 7

这对任何nxn矩阵都是可展开的。 在代码中快速应用这个概念:

void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
    mat[r1][c1] ^= mat[r2][c2];
    mat[r2][c2] ^= mat[r1][c1];
    mat[r1][c1] ^= mat[r2][c2];
}

void transpose(int** mat, int size)
{
    for (int i = 0; i < size; i++)
    {
        for (int j = (i + 1); j < size; j++)
        {
            swapInSpace(mat, i, j, j, i);
        }
    }
}

void rotate(int** mat, int size)
{
    //Get transpose
    transpose(mat, size);

    //Swap columns
    for (int i = 0; i < size / 2; i++)
    {
        for (int j = 0; j < size; j++)
        {
            swapInSpace(mat, i, j, size - (i + 1), j);
        }
    }
}

这是将数组旋转90度的简单C代码。希望这能有所帮助。

#include <stdio.h>

void main(){
int arr[3][4] =     {85, 2, 85,  4,
                     85, 6,  7, 85,
                     9, 85, 11, 12};


int arr1[4][3];

int i = 0, j = 0;

for(i=0;i<4;i++){
int k = 2;//k = (number of columns in the new array arr1 - 1)
for(j=0;j<3;j++){
arr1[i][j]=arr[k][i];
k--;
}
}

int l, m;
for(l=0;l<4;l++){
for(m=0;m<3;m++){
printf("%d ", arr1[l][m]);
}
printf("\n");
}
}//end main

当前所有的解决方案都有O(n^2)开销作为临时空间(这不包括那些肮脏的OOP骗子!)这里有一个内存占用为O(1)的解决方案,将矩阵原地右转90度。该死的延展性,这玩意儿跑得很快!

#include <algorithm>
#include <cstddef>

// Rotates an NxN matrix of type T 90 degrees to the right.
template <typename T, size_t N>
void rotate_matrix(T (&matrix)[N][N])
{
    for(size_t i = 0; i < N; ++i)
        for(size_t j = 0; j <= (N-i); ++j)
            std::swap(matrix[i][j], matrix[j][i]);
}

免责声明:我实际上并没有测试这个。让我们玩打虫游戏吧!

在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)

这是c#的

int[,] array = new int[4,4] {
    { 1,2,3,4 },
    { 5,6,7,8 },
    { 9,0,1,2 },
    { 3,4,5,6 }
};

int[,] rotated = RotateMatrix(array, 4);

static int[,] RotateMatrix(int[,] matrix, int n) {
    int[,] ret = new int[n, n];

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ret[i, j] = matrix[n - j - 1, i];
        }
    }

    return ret;
}