原地矩陣旋轉

我發現一個有趣的問題，要求將NxN矩陣旋轉90度。 C中的遞歸解決方案如下。然而，當我查找其他解決方案時，大多數使用嵌套for循環來完成任務（這似乎工作正常）。嵌套循環實現似乎在O(n^2)時間內運行。原地矩陣旋轉

請參見： How do you rotate a two dimensional array?

我相信遞歸解決方案在O((n^2-n)/2)，這是O(n^2)以及運行。我的問題是雙重的。 1）我的複雜性分析是否正確的遞歸和非遞歸解決方案，以及2）是否有一些高效率或聰明的方法來旋轉我沒有找到的矩陣？

TIA。

#include <stdio.h> 
#include <stdlib.h> 


int SIZE = 0; 


/** 
* In-place, recursive, clockwise, 90 degree matrix rotation. 
*/ 
static void rotate_in_place(int matrix[][SIZE], int n) 
{ 
    if(n < 2) 
     return; 


    int temp1, temp2; 

    for(int i = 0; i < (n-1); i++) 
    { 
     temp1 = matrix[i][n-1]; 
     matrix[i][n-1] = matrix[0][i]; 

     temp2 = matrix[n-1][n-i-1]; 
     matrix[n-1][n-i-1] = temp1; 

     temp1 = matrix[n-i-1][0]; 
     matrix[n-i-1][0] = temp2; 

     matrix[0][i] = temp1; 
    } 


    matrix = ((int*)matrix) + SIZE + 1; 
    n -= 2; 
    rotate_in_place(matrix, n); 
} 


static void print_matrix(int matrix[][SIZE]) 
{ 
    printf("\n"); 
    for(int i = 0; i < SIZE; i++) 
    { 
     for(int j = 0; j < SIZE; j++) 
      printf("%4i ", matrix[i][j]); 

     printf("\n"); 
    } 
} 


int main() 
{ 

    // Create some matrices and rotate them. 
    // 
     int matrices = 10; 

     for(int i = 2; i < matrices; i++) 
     { 
      int matrix[i][i]; 

      int count = 0; 
      for(int j = 0; j < i; j++) 
       for(int k = 0; k < i; k++) 
        matrix[j][k] = ++count; 


      printf("\n\nRotating %ix%i matrix.\n", i, i); 

      SIZE = i; 

      printf("\nOriginal matrix.\n"); 
      print_matrix(matrix); 

      rotate_in_place(matrix, i); 

      printf("\n\nRotated matrix.\n"); 
      print_matrix(matrix); 
     } 


    return EXIT_SUCCESS; 
}

來源

2011-05-05 J. Andrew Laughlin

你必須離開N * N元素到新的位置，所以很難看到它怎麼可能在爲O任何減少（N^2）。 – 2011-05-05 20:57:35

我幾乎不會稱這個解決方案遞歸。你可以用一個「goto」來代替最後的呼叫... – 2011-05-05 21:15:15

因爲需要交換所有元素，所以不能在小於n^2的操作中完成旋轉。但是，通常情況下，由於旋轉垃圾很難，所以我們避免執行它;）

來源

2011-05-05 20:57:28

旋轉！=轉置 – 2011-05-05 21:00:23

好吧，它基本上是一樣的問題，轉置是圍繞對角線旋轉180度。 – 2011-05-05 21:06:36

是的，除了關於對角元素的評論不適用於輪播，所以在這種情況下可能會產生誤導。 – 2011-05-05 22:01:52

您的複雜性分析是正確的，但也很混亂。由於矩陣中元素的數量爲n 2，O（n 2）實際上是輸入大小的線性時間，這是重要的數字。

如果要旋轉後打印整個矩陣，那麼線性時間是最好的。對於其他操作，不要在原地旋轉矩陣，而是編寫一個改變其索引的adapter，這樣就可以訪問旋轉矩陣的元素，而無需在內存中進行實際旋轉。

來源

2011-05-05 21:06:46

到位℃溶液

如下

void rotateRight(int matrix[][SIZE], int length) { 

    int layer = 0; 

    for (int layer = 0; layer < length/2; ++layer) { 

     int first = layer; 
     int last = length - 1 - layer; 

     for (int i = first; i < last; ++i) { 

      int topline = matrix[first][i]; 
      int rightcol = matrix[i][last]; 
      int bottomline = matrix[last][length - layer - 1 - i]; 
      int leftcol = matrix[length - layer - 1 - i][first]; 

      matrix[first][i] = leftcol; 
      matrix[i][last] = topline; 
      matrix[last][length - layer - 1 - i] = rightcol; 
      matrix[length - layer - 1 - i][first] = bottomline; 
     } 
    } 
}

來源

2013-08-13 17:44:35 thiagoh

原地矩陣旋轉

回答

相關問題