Xoay một mảng hai chiều 90 độ

Question

Tôi đang nghiên cứu đoạn mã này khi xoay một ma trận NxN; Tôi đã truy tìm chương trình vô số lần, và tôi hiểu cách xoay vòng thực sự xảy ra. Về cơ bản nó xoay các góc đầu tiên và các phần tử sau các góc theo chiều kim đồng hồ. Tôi chỉ không hiểu một vài dòng, và mã vẫn không phải là "lái xe về nhà" trong bộ não của tôi, vì vậy để nói chuyện. Hãy giúp tôi. Tôi xoay nó 90 độ, cho một ma trận 4x4 như ví dụ truy tìm của tôi.

[1][2][3][4] 
[5][6][7][8] 
[9][0][1][2] 
[3][4][5][6] 

trở thành

[3][9][5][1] 
[4][0][6][2] 
[5][1][7][3] 
[6][2][8][4] 

---

public static void rotate(int[][] matrix, int n){ 
    for(int layer=0; layer < n/2; ++layer) { 
    int first=layer; //It moves from the outside in. 
    int last=n-1-layer; //<--This I do not understand 
    for(int i=first; i<last;++i){ 
     int offset=i-first; //<--A bit confusing for me 

     //save the top left of the matrix 
     int top = matrix[first][i]; 

     //shift left to top; 
     matrix[first][i]=matrix[last-offset][first]; 
     /*I understand that it needs 
     last-offset so that it will go up the column in the matrix, 
     and first signifies it's in the first column*/ 

     //shift bottom to left 
     matrix[last-offset][first]=matrix[last][last-offset]; 
     /*I understand that it needs 
     last-offset so that the number decreases and it may go up the column (first 
     last-offset) and left (latter). */ 

     //shift right to bottom 
     matrix[last][last-offset]=matrix[i][last]; 
     /*I understand that it i so that in the next iteration, it moves down 
     the column*/   



     //rightmost top corner 
     matrix[i][last]=top; 
     } 
    } 

} 

Answer 1

Nó dễ dàng hơn để hiểu một thuật toán như thế này nếu bạn vẽ một sơ đồ, vì vậy tôi làm một pic nhanh chóng trong Paint để chứng minh cho một ma trận 5x5: D

Vòng lặp bên ngoài for(int layer=0; layer < n/2; ++layer) lặp lại qua các lớp từ ngoài vào trong. Lớp ngoài (lớp 0) được mô tả bởi các phần tử màu. Mỗi lớp có hiệu quả là một hình vuông của các yếu tố yêu cầu xoay. Đối với lớp n = 5, sẽ nhận giá trị từ 0 đến 1 vì có 2 lớp vì chúng ta có thể bỏ qua phần tử/lớp trung tâm không bị ảnh hưởng bởi xoay vòng. trước tiên và cuối cùng tham chiếu đến các hàng/cột đầu tiên và cuối cùng của các phần tử cho một lớp; ví dụ. lớp 0 có các yếu tố từ Row/Column đầu tiên = 0-cuối cùng = 4 và lớp 1 từ Row/Column 1 tới 3.

Sau đó, cho mỗi lớp/vuông, khu vực nội for(int i=first; i<last;++i) vòng xoay nó bằng cách quay 4 các phần tử trong mỗi lần lặp. Bù đắp thể hiện khoảng cách dọc theo các cạnh của hình vuông. Đối với 5x5 của chúng tôi bên dưới, trước tiên chúng tôi xoay các phần tử màu đỏ (offset = 0), sau đó là màu vàng (offset = 1), sau đó là màu xanh lá cây và màu xanh dương. Mũi tên 1-5 thể hiện vòng quay 4 phần tử cho các phần tử màu đỏ và 6+ cho phần còn lại được thực hiện theo cùng một kiểu. Lưu ý cách xoay vòng phần tử 4 về bản chất là một trao đổi vòng tròn 5 nhiệm vụ với nhiệm vụ đầu tiên tạm thời bỏ qua một phần tử. Các bình luận //save the top left of the matrix cho nhiệm vụ này là gây hiểu nhầm vì ma trận [đầu tiên] [i] không nhất thiết phải ở trên cùng bên trái của ma trận hoặc thậm chí là lớp cho vấn đề đó. Ngoài ra, lưu ý rằng các chỉ mục hàng/cột của các phần tử được xoay đôi khi tỷ lệ thuận với bù đắp và đôi khi tỷ lệ thuận với nghịch đảo của nó, cuối cùng - offset.

Chúng tôi di chuyển dọc theo các cạnh của lớp ngoài (được mô tả bằng đầu tiên = 0 và cuối = 4) theo cách này, sau đó di chuyển lên lớp bên trong (đầu tiên = 1 và cuối = 3) và thực hiện tương tự ở đó. Cuối cùng, chúng tôi nhấn trung tâm và chúng tôi đã hoàn thành.

Answer 2

Điều này kích hoạt WTF. Cách đơn giản nhất để xoay một ma trận tại chỗ là bởi

• đầu tiên transposing ma trận (swap M [i, j] với M [j, i])
• sau đó trao đổi M [i, j] với M [i, nColumns - j]

Khi ma trận là cột lớn, thao tác thứ hai là hoán đổi cột và do đó có các thuộc tính địa phương dữ liệu tốt. Nếu ma trận là hàng chính, sau đó lần đầu tiên hoán đổi hàng, và sau đó transpose.

Answer 3

Dưới đây là một cách đệ quy giải quyết này:

// xoay một mảng 2 D (MXN) bằng 90 độ

public void rotateArray(int[][] inputArray) { 
    System.out.println("Input Array: "); 
    print2D(inputArray); 
    rotateArray(inputArray, 0, 0, inputArray.length - 1, 
      inputArray[0].length - 1); 
    System.out.println("\n\nOutput Array: "); 
    print2D(inputArray); 

} 

public void rotateArray(int[][] inputArray, int currentRow, 
     int currentColumn, int lastRow, int lastColumn) { 

    // condition to come out of recursion. 
    // if all rows are covered or all columns are covered (all layers 
    // covered) 
    if (currentRow >= lastRow || currentColumn >= lastColumn) 
     return; 
    // rotating the corner elements first 
    int top = inputArray[currentRow][currentColumn]; 
    inputArray[currentRow][currentColumn] = inputArray[lastRow][currentColumn]; 
    inputArray[lastRow][currentColumn] = inputArray[lastRow][lastColumn]; 
    inputArray[lastRow][lastColumn] = inputArray[currentRow][lastColumn]; 
    inputArray[currentRow][lastColumn] = top; 

    // clockwise rotation of remaining elements in the current layer 
    for (int i = currentColumn + 1; i < lastColumn; i++) { 
     int temp = inputArray[currentRow][i]; 
     inputArray[currentRow][i] = inputArray[lastRow - i][currentColumn]; 
     inputArray[lastRow - i][currentColumn] = inputArray[lastRow][lastColumn 
       - i]; 
     inputArray[lastRow][lastColumn - i] = inputArray[currentRow + i][lastColumn]; 
     inputArray[currentRow + i][lastColumn] = temp; 
    } 

    // call recursion on remaining layers 
    rotateArray(inputArray, ++currentRow, ++currentColumn, --lastRow, 
      --lastColumn); 
}