3

Given a 2D NxN matrix, visualize it as concentric circles. You have to find the rotated matrix where each element in the circle is rotated by 1 position layer by layer in an alternate clockwise and anticlockwise direction. All rotations should be in-place.

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

should get transformed to 

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

I thought about the solution

1> For clockwise circle rotation, read elements in the order

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

2> For anti-clockwise circle rotation, read elements in the order

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

Code

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
        }       
}

Is there any better approach to solve this problem in O(n2) or better ?

4

6 回答 6

4

由于您的数组大小为 N*N，并且所需的计算要求每个元素至少访问一次，因此没有比O(n^2)使用二维数组更好的解决方案。

我认为如果必须在同一个阵列上一次性完成操作，您的解决方案会很好。

如果您必须在同一个输入数组上多次执行此操作，最好从输入数组创建圆。circle的数据结构应该是CLL（循环链表）。因此，多次执行该操作将是小菜一碟，因为您必须根据方向更改存储圆信息的 CLL 的根元素。

于 2012-04-15T11:01:56.197 回答
1

我认为这可以在 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();

于 2015-01-11T17:30:33.003 回答
1

我最近在一次求职面试中遇到了这个问题，但我在不到一小时的时间内没有解决。

然后我回到家并用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;
    }

}
于 2015-09-18T17:33:15.897 回答
0 
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();
       }
    }
}
于 2015-01-13T09:05:44.677 回答
0

顺时针旋转 90 度。Python3 中的 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
于 2019-05-19T11:51:11.327 回答
0 
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;
    }
}
于 2017-04-02T02:21:48.217 回答