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


当前回答

虽然旋转数据可能是必要的(也许是为了更新物理存储的表示),但在数组访问上添加一层间接层(也许是一个接口)会变得更简单,可能更性能:

interface IReadableMatrix
{
    int GetValue(int x, int y);
}

如果你的矩阵已经实现了这个接口,那么它可以通过这样一个装饰器类来旋转:

class RotatedMatrix : IReadableMatrix
{
    private readonly IReadableMatrix _baseMatrix;

    public RotatedMatrix(IReadableMatrix baseMatrix)
    {
        _baseMatrix = baseMatrix;
    }

    int GetValue(int x, int y)
    {
        // transpose x and y dimensions
        return _baseMatrix(y, x);
    }
}

旋转+90/-90/180度,水平/垂直翻转和缩放都可以以这种方式实现。

Performance would need to be measured in your specific scenario. However the O(n^2) operation has now been replaced with an O(1) call. It's a virtual method call which is slower than direct array access, so it depends upon how frequently the rotated array is used after rotation. If it's used once, then this approach would definitely win. If it's rotated then used in a long-running system for days, then in-place rotation might perform better. It also depends whether you can accept the up-front cost.

与所有性能问题一样,测量,测量,测量!

其他回答

这是一个Javascript解决方案:

const transpose = m => m[0].map((x,i) => m.map(x => x[i]));

a: // original matrix
123
456
789

transpose(a).reverse(); // rotate 90 degrees counter clockwise 
369
258
147

transpose(a.slice().reverse()); // rotate 90 degrees clockwise 
741
852
963

transpose(transpose(a.slice().reverse()).slice().reverse())
// rotate 180 degrees 
987
654
321

这是一个如今被高估的面试问题。

我的建议是:不要让面试官用他们关于解决这个问题的疯狂建议把你弄糊涂了。使用白板绘制输入数组的索引,然后绘制输出数组的索引。旋转前后的列分度示例如下:

30 --> 00
20 --> 01
10 --> 02
00 --> 03

31 --> 10
21 --> 11
11 --> 12
01 --> 13

注意旋转后的数字模式。

下面提供了一个简洁的Java解决方案。经过测试,它是有效的:

 Input:
    M A C P 
    B N L D 
    Y E T S 
    I W R Z 

    Output:
    I Y B M 
    W E N A 
    R T L C 
    Z S D P 

/**
 * (c) @author "G A N MOHIM"
 * Oct 3, 2015
 * RotateArrayNintyDegree.java
 */
package rotatearray;

public class RotateArrayNintyDegree {

    public char[][] rotateArrayNinetyDegree(char[][] input) {
        int k; // k is used to generate index for output array

        char[][] output = new char[input.length] [input[0].length];

        for (int i = 0; i < input.length; i++) {
            k = 0;
            for (int j = input.length-1; j >= 0; j--) {
                output[i][k] = input[j][i]; // note how i is used as column index, and j as row
                k++;
            }
        }

        return output;
    }

    public void printArray(char[][] charArray) {
        for (int i = 0; i < charArray.length; i++) {
            for (int j = 0; j < charArray[0].length; j++) {
                System.out.print(charArray[i][j] + " ");
            }
            System.out.println();
        }


    }

    public static void main(String[] args) {
        char[][] input = 
                { {'M', 'A', 'C', 'P'},
                  {'B', 'N', 'L', 'D'},
                  {'Y', 'E', 'T', 'S'},
                  {'I', 'W', 'R', 'Z'}
                };

        char[][] output = new char[input.length] [input[0].length];

        RotateArrayNintyDegree rotationObj = new RotateArrayNintyDegree();
        rotationObj.printArray(input);

        System.out.println("\n");
        output = rotationObj.rotateArrayNinetyDegree(input);
        rotationObj.printArray(output);

    }

}

已经有很多答案了,我发现两个声称O(1)时间复杂度。真正的O(1)算法是保持数组存储不变,并改变索引其元素的方式。这里的目标是不消耗额外的内存,也不需要额外的时间来迭代数据。

旋转90度,-90度和180度是简单的转换,只要你知道你的2D数组中有多少行和列就可以执行;要将任何向量旋转90度,交换轴并与Y轴相反。对于-90度,交换轴和X轴。对于180度,两个坐标轴都是负的,不交换。

进一步的转换是可能的,例如通过独立地否定轴来水平和/或垂直地镜像。

这可以通过访问器方法来实现。下面的例子是JavaScript函数,但是这些概念同样适用于所有语言。

//按列/行顺序获取数组元素 var getArray2d =函数(a, x, y) { 返回一个[y] [x]; }; / /演示 Var arr = [ [5,4,6], [1,7,9], [- 2,11,0], [8,21, -3], [3, -1, 2] ]; Var newar = []; arr[0]. foreach (() => newarr。push(新数组(arr.length))); For (var I = 0;I < newar .length;我+ +){ For (var j = 0;J < newarr[0].length;j + +) { newarr[i][j] = getArray2d(arr, i, j); } } console.log (newarr);

// Get an array element rotated 90 degrees clockwise function getArray2dCW(a, x, y) { var t = x; x = y; y = a.length - t - 1; return a[y][x]; } //demo var arr = [ [5, 4, 6], [1, 7, 9], [-2, 11, 0], [8, 21, -3], [3, -1, 2] ]; var newarr = []; arr[0].forEach(() => newarr.push(new Array(arr.length))); for (var i = 0; i < newarr[0].length; i++) { for (var j = 0; j < newarr.length; j++) { newarr[j][i] = getArray2dCW(arr, i, j); } } console.log(newarr);

// Get an array element rotated 90 degrees counter-clockwise function getArray2dCCW(a, x, y) { var t = x; x = a[0].length - y - 1; y = t; return a[y][x]; } //demo var arr = [ [5, 4, 6], [1, 7, 9], [-2, 11, 0], [8, 21, -3], [3, -1, 2] ]; var newarr = []; arr[0].forEach(() => newarr.push(new Array(arr.length))); for (var i = 0; i < newarr[0].length; i++) { for (var j = 0; j < newarr.length; j++) { newarr[j][i] = getArray2dCCW(arr, i, j); } } console.log(newarr);

// Get an array element rotated 180 degrees function getArray2d180(a, x, y) { x = a[0].length - x - 1; y = a.length - y - 1; return a[y][x]; } //demo var arr = [ [5, 4, 6], [1, 7, 9], [-2, 11, 0], [8, 21, -3], [3, -1, 2] ]; var newarr = []; arr.forEach(() => newarr.push(new Array(arr[0].length))); for (var i = 0; i < newarr[0].length; i++) { for (var j = 0; j < newarr.length; j++) { newarr[j][i] = getArray2d180(arr, i, j); } } console.log(newarr);

这段代码假设有一个嵌套数组的数组,其中每个内部数组都是一行。

该方法允许您读取(或写入)元素(甚至是随机顺序),就像数组已经旋转或转换一样。现在只要选择正确的函数来调用,可能是通过引用,然后就可以了!

这个概念可以扩展为通过访问器方法附加地(非破坏性地)应用转换。包括任意角度旋转和缩放。

下面是Java语言:

public static void rotateInPlace(int[][] m) {
    for(int layer = 0; layer < m.length/2; layer++){
        int first = layer;
        int last = m.length - 1 - first;
        for(int i = first; i < last; i ++){
            int offset = i - first;
            int top = m[first][i];
            m[first][i] = m[last - offset][first];
            m[last - offset][first] = m[last][last - offset];
            m[last][last - offset] = m[i][last];
            m[i][last] = top;
        }
    }
}

PHP:

array_unshift($array, null);
$array = call_user_func_array("array_map", $array);

如果你需要旋转矩形二维阵列90度,在上面的代码之前或之后添加以下一行(取决于你需要的旋转方向):

$array = array_reverse($array);