在同心圆中旋转一个2D的NxN矩阵

Question

给定一个2D的NxN矩阵，将其视为同心圆。你需要找到旋转后的矩阵，其中每个圆中的元素按交替顺序顺时针和逆时针方向旋转1个位置。所有旋转都应该原地完成。

2 3 4 5
1 6 7 8
4 2 1 9
5 3 2 4

应该被转换为

。

1 2 3 4 
4 7 1 5 
5 6 2 8 
3 2 4 9 

我考虑了解决方案。

1> 对于顺时针圆形旋转，请按顺序读取元素。

i -> 0 to n-1 and j = 0
j -> 0 to n-1 and i = n-1
i -> n-1 to 0 and j = n-1
j -> n-1 to 0 and i = 0

对于逆时针旋转圆形，按照以下顺序阅读元素。

j -> 0 to n-1 and i = 0
i -> 0 to n-1 and j = n-1
j -> n-1 to 0 and i = n-1
i -> n-1 to 0 and j = 0

"代码"

for(int cnt = 0; cnt < n/2; cnt++)
    {   
        if(cnt%2 == 0) // Clockwise
        {   
            i = cnt; j = cnt;
            // while loops for each case
        }
        else // anti-clockwise
        {
            i = cnt; j = cnt;
            // while loops for each case
        }       
}

有没有更好的方法来解决这个问题，时间复杂度为O(n2)或更好？

- w00t

---

你有完整的代码吗？ - Ofir Attia

Answer 1

由于您的数组大小为N * N，且所需计算要求至少访问每个元素一次，因此使用二维数组的解决方案不能比O(n ^ 2)更好。如果操作只需要在同一个数组上执行一次，则您的解决方案应该是可以的。

如果您需要在同一输入数组上多次执行此操作，则最好从输入数组创建圆形。圆形的数据结构应该是CLL（循环链表）。因此，多次执行操作将变得非常容易，因为您只需根据方向更改存储圆形信息的CLL的根元素即可。

- Tejas Patil

Answer 2

我认为这个问题可以轻松地在O(n)时间内原地解决。

（注意：O（N）其中N是矩阵元素的总数）

以下解决方案不使用四个连续循环，而是使用一个小的 [X,Y] 增量表来描述当前坐标和下一个坐标之间的差异。当下一个坐标无效（即在当前窗口之外）时，表本身的索引会前进，并重复查找。算法从完整窗口开始，并在每次嵌套循环完成时从每个边缘减去一个元素。整个过程一直重复，直到定义为[minX,minY,maxX,maxY]的窗口有效（即包含至少2x2个元素）。

此解决方案不实现交换cw和ccw，但这是最容易添加的部分。

function pad(s, n) {
  while(s.length < n)
    s = " " + s;
  return s;
}

// Create a matrix of [WxH] size.
function Matrix(w, h, data) {
  if (Array.isArray(data)) {
    if (data.length !== w * h)
      throw new Error("Data.length has to match the size " + (w * h) + ".");
  }
  else {
    var n = typeof data === "number" ? data : 0.0;
    data = [];
    for (var i = 0; i < w*h; i++) data.push(n);
  }

  this.w = w;
  this.h = h;
  this.data = data;
}

// Get value at [x, y]
Matrix.prototype.get = function(x, y) {
  if (x < 0 || x >= this.w || y < 0 || y >= this.h)
    throw new Error("Index [" + x + ", " + y + "] out of bounds");
  return this.data[y * this.w + x];
}

// Set value at [x, y] and return the previous value.
Matrix.prototype.set = function(x, y, value) {
  if (x < 0 || x >= this.w || y < 0 || y >= this.h)
    throw new Error("Index [" + x + ", " + y + "] out of bounds");

  var i = y * this.w + x;
  var prev = this.data[i];

  this.data[i] = value;
  return prev;
}

// Log the matrix data.
Matrix.prototype.dump = function() {
  var s = "["
  var i = 0;
  for (var y = 0; y < this.h; y++) {
    for (var x = 0; x < this.w; x++, i++) {
      s += pad("" + this.data[i], 2);
      if (x !== this.w - 1)
        s += ","
    }
    if (y !== this.h - 1)
      s += ",\n ";
  }
  s += "]";
  console.log(s);
}

// Shift, `dir` can be "cw" or "ccw".
Matrix.prototype.shift = function(dir) {
  var instructions = {
    cw : [1, 0, 0, 1,-1, 0, 0,-1],
    ccw: [0, 1, 1, 0, 0,-1,-1, 0]
  };
 
  var inst = instructions[dir];

  // A window, shrink by one from each side after the nested loop is done.
  var minX = 0;
  var minY = 0;
  var maxX = this.w - 1;
  var maxY = this.h - 1;

  while (minX < maxX && minY < maxY) {
    // Always start at the top-left corner and iterate.
    var x0 = minX;
    var y0 = minY;
    var v0 = this.get(x0, y0);
    var n = 0;

    for (;;) {
      var x1 = x0 + inst[n + 0];
      var y1 = y0 + inst[n + 1];

      if (x1 < minX || x1 > maxX || y1 < minY || y1 > maxY) {
        n += 2;
        x1 = x0 + inst[n + 0];
        y1 = y0 + inst[n + 1];
      }

      v0 = this.set(x1, y1, v0);

      // Last one.
      if (x1 === minX && y1 === minY)
        break;

      x0 = x1;
      y0 = y1;
    }

    minX++;
    minY++;
    maxX--;
    maxY--;
  }
}

var a = new Matrix(3, 3, [
  1,2,3,
  4,5,6,
  7,8,9,
]);

a.dump();
a.shift("cw");
a.dump();

var b = new Matrix(4, 4, [
  1 ,2 ,3 ,4 ,
  5 ,6 ,7 ,8 ,
  9 ,10,11,12,
  13,14,15,16
]);

b.dump();
b.shift("ccw");
b.dump();

- Petr

---

它肯定是O(n)的；从代码中可以看出来。如果你不确定，可以试一下。 - Petr

尝试了一下，我已经计算了您的代码达到for(;;)语句的次数，这将计算重复最多的操作组的次数，从而确定复杂度。以下是结果：n = 3 -> 8 次 n = 4 -> 16 次 n = 5 -> 24 次 n = 6 -> 36 次 [...]因此，当n为偶数时，它是n^2，当n为奇数时，它是(n^2)-1，这给我们带来了O(n^2)。这很有道理，因为当n为奇数时，唯一未被触及的元素就在中间。正如Tejas Patil所说，没有比O(n^2)更少的方法来完成这项任务。无论如何，非常好的答案，非常聪明的算法。 - lotif

我认为有一些误解。对我来说，代码的时间复杂度是O(N)，因为AxB矩阵总共有N个元素，所以它是线性时间，因为每个元素都会被访问一次（更具体地说，读取和写入一次）。请注意，矩阵不必是正方形，代码将在任何矩阵大小下运行。换句话说，我计算了数据元素的数量，并根据此计算了复杂度。例如填充矩阵：for (var i = 0; i < w*h; i++) data.push(n);对我来说也是线性的，等等 :) 我希望我已经讲清楚了，感谢您的意见。 - Petr

顺便说一下，我写的代码对于小矩阵来说效果很好，但是在进行垂直位移时，对于大矩阵的表现不佳。原因是它基本上会进行随机内存访问。可以通过始终按顺序访问矩阵元素来改进代码（这意味着始终在水平方向上进行位移），但这将使解决方案变得非常复杂，如果这是我的问题，我就不会使用JavaScript来回答。然而，如果你正在面试，这是应该提到的事情。 - Petr

非常棒的解决方案。它是O(n)，因为您重新定义了n的含义。当使用大多数人与问题相关联的n值（一个外部数组的长度）时，它是O(n^2)。所以曾经的O(n) = O(3^2) = 8现在变成了O(n) = O(9) ~= 8。因此，改变n不仅影响了复杂度符号的输入，还影响了公式和结果。请注意，`=`是因为上面引用的数字似乎不是完美的平方数，但接近于它们。也许它们没有被正确计算。 - Samuel Neff

Answer 3

我最近在一次工作面试中遇到了这个问题，但我未能在一个小时内解决它。

后来我回到家，在 Java 中编写了下面的递归代码。我相信它的时间复杂度是 O(n^2)。你也可以在这里查看代码：https://github.com/lotif/rotateMatrix

你首先需要输入（正方形）矩阵的维度，然后按行输入矩阵中的数字，用空格隔开。例如：

3

1 2 3

4 5 6

7 8 9

它将以同心圆顺时针旋转矩阵。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class RotateMatrix {

    public static void main(String args[] ) throws Exception {
        Scanner s = new Scanner(System.in);

        int d = s.nextInt();

        int[][] matrix = new int[d][d];
        for(int i = 0; i < d; i++) {
            for(int j = 0; j < d; j++) {
                matrix[i][j] = Integer.parseInt(s.next());
            }
        }

        matrix = rotate(matrix);

        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix.length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }

        s.close();
    }

    public static int[][] rotate(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix.length == 1) {
            return matrix;
        }

        List<Integer> outerCircle = getOuterCircle(matrix);
        matrix = removeOuterCircle(matrix);
        //rotating outer circle
        outerCircle.add(0, outerCircle.remove(outerCircle.size() - 1));

        matrix = rotate(matrix);

        matrix = addOuterCircle(outerCircle, matrix);

        return matrix;

    }

    private static int[][] addOuterCircle(List<Integer> outerCircle, int[][] matrix) {

        int d = matrix.length + 2;
        int[][] newMatrix = new int[d][d];

        //Adding the outer circle to the matrix
        for(int j = 0; j < d; j++) {
            newMatrix[0][j] = outerCircle.remove(0);
        }
        for(int i = 1; i < d; i++) {
            newMatrix[i][d-1] = outerCircle.remove(0);
        }
        for(int j = d-2; j >= 0; j--) {
            newMatrix[d-1][j] = outerCircle.remove(0);
        }
        for(int i = d-2; i >= 1; i--) {
            newMatrix[i][0] = outerCircle.remove(0);
        }

        //Adding the inner matrix
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[i].length; j++) {
                newMatrix[i + 1][j + 1] = matrix[i][j];
            }
        }

        return newMatrix;

    }

    private static List<Integer> getOuterCircle(int[][] matrix) {
        int d = matrix.length;

        List<Integer> outerCircle = new ArrayList<Integer>();

        for(int j = 0; j < d; j++) {
            outerCircle.add(matrix[0][j]);
        }
        for(int i = 1; i < d; i++) {
            outerCircle.add(matrix[i][d-1]);
        }
        for(int j = d-2; j >= 0; j--) {
            outerCircle.add(matrix[d-1][j]);
        }
        for(int i = d-2; i >= 1; i--) {
            outerCircle.add(matrix[i][0]);
        }

        return outerCircle;
    }

    private static int[][] removeOuterCircle(int[][] matrix) {      
        int d = matrix.length;
        int[][] newMatrix = new int[d-2][d-2];

        for(int i = 1; i < d-1; i++) {
            for(int j = 1; j < d-1; j++) {
                newMatrix[i-1][j-1] = matrix[i][j];
            }
        }

        return newMatrix;
    }

}

- lotif

Answer 4

public class ShiftArray {
    static void shiftArray(int[][]a, int index, int n) {
       if ((n%2 == 0) && (index >= n/2))
           return;
       if ((n%2 != 0) && (index > n/2))
           return;

       int tempRowTopLast = a[index][n-1-index]; 
       int tempColRightLast = a[n-1-index][n-1-index];
       int tempRowBottomLast = a[n-1-index][index]; 
       int tempColLeftLast = a[index][index];

       int temp, temp2;

       temp = tempColLeftLast; 

       for (int k = index + 1; k < n-index; k++) {
           temp2 = a[index][k];
           a[index][k] = temp;
           temp = temp2;
       }

       temp = tempRowTopLast; 
       for (int k = index + 1; k < n-index; k++) {
           temp2 = a[k][n-1-index];
           a[k][n-1-index] = temp; 
           temp = temp2; 
       }

       temp = tempColRightLast; 
       for (int k = n-2-index; k >=index; k--) {
           temp2 = a[n-1-index][k];
           a[n-1-index][k] = temp; 
           temp = temp2; 
       }

       temp = tempRowBottomLast;
       for (int k = n-2-index; k >=index; k--) {
           temp2 = a[k][index];
           a[k][index] = temp;
           temp = temp2;
       } 

       shiftArray(a, index+1, n);

    }

    public static void main(String[] args) {
        int a[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

        shiftArray(a, 0, 3);
        System.out.println("Rotated array...");

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(a[i][j] + ",");
            }
            System.out.println();
       }
    }
}

- Saurav Biswas

---

你的回答需要更多的解释。 - ryanyuyu

Answer 5

import java.util.Scanner;

public class RotateMatrix
{
    static int rows = 0;
    static int cols = 0;

    public static void main(String[] args)
    {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        rows = scan.nextInt();
        cols = scan.nextInt();
        int rots = scan.nextInt();
        int[][] matrix = new int[rows][cols];
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                matrix[i][j] = scan.nextInt();
            }
        }
        for (int i = 0; i < rots; i++)
            rotate(matrix, 0, rows - 1, 0, cols - 1);

        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
        scan.close();
    }

    public static int[][] rotate(int[][] arr, int rowStart, int rowEnd, int colStart, int colEnd)
    {

        if (rowStart == rowEnd && colStart == colEnd)
        {
            return arr;
        }
        if (rowStart > rowEnd || colStart > colEnd)
        {
            return arr;
        }

        int temp = arr[rowStart][colStart];
        for (int j = colStart; j < colEnd; j++)
        {
            arr[colStart][j] = arr[colStart][j + 1];
        }
        for (int i = rowStart; i < rowEnd; i++)
        {
            arr[i][colEnd] = arr[i + 1][colEnd];
        }
        for (int i = colEnd; i > colStart; i--)
        {
            arr[rowEnd][i] = arr[rowEnd][i - 1];
        }
        for (int i = rowEnd; i > rowStart; i--)
        {
            arr[i][colStart] = arr[i - 1][colStart];
        }

        if (rows == 1)
        {
            arr[colEnd][rowStart] = temp;
        }
        else
            arr[rowStart + 1][colStart] = temp;

        System.out.println("-----------------------------------------\n");
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("-----------------------------------------\n");
        rotate(arr, rowStart + 1, rowEnd - 1, colStart + 1, colEnd - 1);
        return arr;
    }
}

- anuj kumar

Answer 6

Python3中顺时针旋转90度。时间复杂度为O(n^2)，空间复杂度为O(1)：

# @param A : list of list of integers
# @return the same list modified
def rotate(A):
    for row in range(len(A) // 2):
        for col in range(row, len(A)-1 - row): # First col already takes care of last.
            r = row
            c = col
            tmp1 = A[r][c]
            while True:
                next_r = c
                next_c = len(A) - 1 - r
                tmp2 = A[next_r][next_c]
                A[next_r][next_c] = tmp1
                if next_r == row and next_c == col:
                    break
                tmp1 = tmp2
                r = next_r
                c = next_c
    return A

- Elias Mueller

---

考虑添加一些注释。仅有代码的答案是不被建议的。 - YetAnotherBot