我发现了一个有趣的问题,要求将一个NxN矩阵就地旋转90度。我的递归解决方案使用C语言编写,如下所示。然而,当我查找其他解决方案时,大多数都使用嵌套的for循环来完成任务(似乎也可以正常工作)。嵌套循环实现似乎在O(n^2)时间内运行。
参见: 如何旋转二维数组? 我认为递归解决方案的复杂度分析是正确的,分别为O((n^2-n)/2)和O(n^2)。我的问题有两个。1)我的复杂度分析对递归和非递归解决方案都正确吗?2)是否存在一些高效或巧妙的方法来旋转矩阵,而我还没有发现?
谢谢您。
参见: 如何旋转二维数组? 我认为递归解决方案的复杂度分析是正确的,分别为O((n^2-n)/2)和O(n^2)。我的问题有两个。1)我的复杂度分析对递归和非递归解决方案都正确吗?2)是否存在一些高效或巧妙的方法来旋转矩阵,而我还没有发现?
谢谢您。
#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;
}
goto
替换最后一次调用... - R.. GitHub STOP HELPING ICE