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


当前回答

试试我图书馆的算盘——常见的:

@Test
public void test_42519() throws Exception {
    final IntMatrix matrix = IntMatrix.range(0, 16).reshape(4);

    N.println("======= original =======================");
    matrix.println();
    // print out:
    //    [0, 1, 2, 3]
    //    [4, 5, 6, 7]
    //    [8, 9, 10, 11]
    //    [12, 13, 14, 15]

    N.println("======= rotate 90 ======================");
    matrix.rotate90().println();
    // print out:
    //    [12, 8, 4, 0]
    //    [13, 9, 5, 1]
    //    [14, 10, 6, 2]
    //    [15, 11, 7, 3]

    N.println("======= rotate 180 =====================");
    matrix.rotate180().println();
    // print out:
    //    [15, 14, 13, 12]
    //    [11, 10, 9, 8]
    //    [7, 6, 5, 4]
    //    [3, 2, 1, 0]

    N.println("======= rotate 270 ======================");
    matrix.rotate270().println();
    // print out:
    //    [3, 7, 11, 15]
    //    [2, 6, 10, 14]
    //    [1, 5, 9, 13]
    //    [0, 4, 8, 12]

    N.println("======= transpose =======================");
    matrix.transpose().println();
    // print out:
    //    [0, 4, 8, 12]
    //    [1, 5, 9, 13]
    //    [2, 6, 10, 14]
    //    [3, 7, 11, 15]

    final IntMatrix bigMatrix = IntMatrix.range(0, 10000_0000).reshape(10000);

    // It take about 2 seconds to rotate 10000 X 10000 matrix.
    Profiler.run(1, 2, 3, "sequential", () -> bigMatrix.rotate90()).printResult();

    // Want faster? Go parallel. 1 second to rotate 10000 X 10000 matrix.
    final int[][] a = bigMatrix.array();
    final int[][] c = new int[a[0].length][a.length];
    final int n = a.length;
    final int threadNum = 4;

    Profiler.run(1, 2, 3, "parallel", () -> {
        IntStream.range(0, n).parallel(threadNum).forEach(i -> {
            for (int j = 0; j < n; j++) {
                c[i][j] = a[n - j - 1][i];
            }
        });
    }).printResult();
}

其他回答

一些人已经举了一些例子,其中涉及到创建一个新数组。

还有一些需要考虑的事情:

(a)不实际移动数据,只需以不同的方式遍历“旋转”的数组。

(b)就地轮换可能有点棘手。您需要一点空白的地方(大概相当于一行或一列的大小)。有一篇古老的ACM论文是关于进行原地转置的(http://doi.acm.org/10.1145/355719.355729),但是他们的示例代码是令人讨厌的充满goto的FORTRAN。

附录:

http://doi.acm.org/10.1145/355611.355612是另一种更优越的就地转置算法。

O(1)内存算法:

旋转最外层的数据,然后你可以得到以下结果: [3] [9] [5] [1] [4] [6] [7] [2] [5] [0] [1] [3] [6] [2] [8] [4]

做这个旋转,我们知道

    dest[j][n-1-i] = src[i][j]

观察下图: A (0,0) -> A (0,3) A (0,3) -> A (3,3) A (3,3) -> A (3,0) A (3,0) -> A (0,0)

因此它是一个圆,你可以在一个循环中旋转N个元素。做这个N-1循环,然后你可以旋转最外层的元素。

对于2X2,内部也是一样的问题。

因此,我们可以得出如下结论:

function rotate(array, N)
{
    Rotate outer-most data
    rotate a new array with N-2 or you can do the similar action following step1
}

顺时针或逆时针旋转2D数组的常用方法。

顺时针旋转 首先颠倒上下,然后交换对称 1 2 3 7 8 9 7 4 4 5 6 => 4 5 6 => 8 5 7 8 9 1 2 3 9 6 3

void rotate(vector<vector<int> > &matrix) {
    reverse(matrix.begin(), matrix.end());
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = i + 1; j < matrix[i].size(); ++j)
            swap(matrix[i][j], matrix[j][i]);
    }
}

逆时针方向旋转 首先从左到右反向,然后交换对称 1 2 3 3 2 1 3 6 9 4 5 6 => 6 5 4 => 2 5 7 8 9 9 8 7 1 4 7

void anti_rotate(vector<vector<int> > &matrix) {
    for (auto vi : matrix) reverse(vi.begin(), vi.end());
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = i + 1; j < matrix[i].size(); ++j)
            swap(matrix[i][j], matrix[j][i]);
    }
}

下面是我的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

下面是Java版本:

public static void rightRotate(int[][] matrix, int n) {
    for (int layer = 0; layer < n / 2; layer++) {
        int first = layer;
        int last = n - 1 - first;
        for (int i = first; i < last; i++) {
           int offset = i - first;
           int temp = matrix[first][i];
           matrix[first][i] = matrix[last-offset][first];
           matrix[last-offset][first] = matrix[last][last-offset];
           matrix[last][last-offset] = matrix[i][last];
           matrix[i][last] = temp;
        }
    }
}

该方法首先旋转最外层,然后按顺序移动到内层。