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


当前回答

C代码的矩阵旋转90度顺时针在任何M*N矩阵的地方

void rotateInPlace(int * arr[size][size], int row, int column){
    int i, j;
    int temp = row>column?row:column;
    int flipTill = row < column ? row : column;
    for(i=0;i<flipTill;i++){
        for(j=0;j<i;j++){
            swapArrayElements(arr, i, j);
        }
    }

    temp = j+1;

    for(i = row>column?i:0; i<row; i++){
            for(j=row<column?temp:0; j<column; j++){
                swapArrayElements(arr, i, j);
            }
    }

    for(i=0;i<column;i++){
        for(j=0;j<row/2;j++){
            temp = arr[i][j];
            arr[i][j] = arr[i][row-j-1];
            arr[i][row-j-1] = temp;
        }
    }
}

其他回答

c#代码将[n,m] 2D数组向右旋转90度

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace MatrixProject
{
    // mattrix class

    class Matrix{
        private int rows;
        private int cols;
        private int[,] matrix;

        public Matrix(int n){
            this.rows = n;
            this.cols = n;
            this.matrix = new int[this.rows,this.cols];

        }

        public Matrix(int n,int m){
            this.rows = n;
            this.cols = m;

            this.matrix = new int[this.rows,this.cols];
        }

        public void Show()
        {
            for (var i = 0; i < this.rows; i++)
            {
                for (var j = 0; j < this.cols; j++) {
                    Console.Write("{0,3}", this.matrix[i, j]);
                }
                Console.WriteLine();
            }                
        }

        public void ReadElements()
        {
           for (var i = 0; i < this.rows; i++)
                for (var j = 0; j < this.cols; j++)
                {
                    Console.Write("element[{0},{1}]=",i,j);
                    this.matrix[i, j] = Convert.ToInt32(Console.ReadLine());
                }            
        }


        // rotate [n,m] 2D array by 90 deg right
        public void Rotate90DegRight()
        {

            // create a mirror of current matrix
            int[,] mirror = this.matrix;

            // create a new matrix
            this.matrix = new int[this.cols, this.rows];

            for (int i = 0; i < this.rows; i++)
            {
                for (int j = 0; j < this.cols; j++)
                {
                    this.matrix[j, this.rows - i - 1] = mirror[i, j];
                }
            }

            // replace cols count with rows count
            int tmp = this.rows;
            this.rows = this.cols;
            this.cols = tmp;           
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Matrix myMatrix = new Matrix(3,4);
            Console.WriteLine("Enter matrix elements:");
            myMatrix.ReadElements();
            Console.WriteLine("Matrix elements are:");
            myMatrix.Show();
            myMatrix.Rotate90DegRight();
            Console.WriteLine("Matrix rotated at 90 deg are:");
            myMatrix.Show();
            Console.ReadLine();
        }
    }
}

结果:

    Enter matrix elements:
    element[0,0]=1
    element[0,1]=2
    element[0,2]=3
    element[0,3]=4
    element[1,0]=5
    element[1,1]=6
    element[1,2]=7
    element[1,3]=8
    element[2,0]=9
    element[2,1]=10
    element[2,2]=11
    element[2,3]=12
    Matrix elements are:
      1  2  3  4
      5  6  7  8
      9 10 11 12
    Matrix rotated at 90 deg are:
      9  5  1
     10  6  2
     11  7  3
     12  8  4

已经有很多答案了,我发现两个声称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);

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

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

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

Javascript解决NxN矩阵与运行时O(N^2)和内存O(1)

  function rotate90(matrix){
    var length = matrix.length
    for(var row = 0; row < (length / 2); row++){
      for(var col = row; col < ( length - 1 - row); col++){
        var tmpVal = matrix[row][col];
        for(var i = 0; i < 4; i++){
          var rowSwap = col;
          var colSwap = (length - 1) - row;
          var poppedVal = matrix[rowSwap][colSwap];
          matrix[rowSwap][colSwap] = tmpVal;
          tmpVal = poppedVal;
          col = colSwap;
          row = rowSwap;
        }
      }
    }
  }

在原地顺时针90度旋转使用矢量矢量..

 #include<iostream>
 #include<vector>
 #include<algorithm>
 using namespace std;
 //Rotate a Matrix by 90 degrees
void rotateMatrix(vector<vector<int> > &matrix){
   int n=matrix.size();
   for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
        swap(matrix[i][j],matrix[j][i]);
    }
 }
     for(int i=0;i<n;i++){
        reverse(matrix[i].begin(),matrix[i].end());
       }
   }

    int main(){

   int n;
   cout<<"enter the size of the matrix:"<<endl;
     while (cin >> n) {
    vector< vector<int> > m;
      cout<<"enter the elements"<<endl;
    for (int i = 0; i < n; i++) {
        m.push_back(vector<int>(n));
        for (int j = 0; j < n; j++)
            scanf("%d", &m[i][j]);
    }
      cout<<"the rotated matrix is:"<<endl;
      rotateMatrix(m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << m[i][j] << ' ';
        cout << endl;
    }
   }
   return 0;
 }
private static int[][] rotate(int[][] matrix, int n) {
    int[][] rotated = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            rotated[i][j] = matrix[n-j-1][i];
        }
    }
    return rotated;
}