旋转一个N*N的矩阵，不准开辟新空间

有没有什么好方法？逐层向里那个我感觉有点难理解，很难面试的时候立马写出来

建议楼主可以看一下Cracking the Code Interview这本书，上面对这道题有比较详细的算法描述。

给个C++的
T为0时表示左右翻转，为1时表示上下翻转。

#include <iostream>
using namespace std;

int main ()
{
        int A[201][201];
        int M, N, T;
        cin >> M >> N >>T;
        for (int i = 0; i < M; i++)
        {
                for (int j = 0; j < N; j++)
                        cin >> A[i][j];
        }
        if ( T == 1)
        {
                for (int i = M - 1; i >= 0; i--)
                {
                        for (int j = 0; j < N; j++)
                                cout << A[i][j] << ' ';       
                        cout << endl;
                }
        }
        else
        {
                for (int i = 0; i < M; i++)
                {
                        for (int j = N -1 ; j >= 0; j--)
                                cout << A[i][j] << ' ';               
                        cout << endl;
                }
        }
        //while (1);
        return 0;
}

MTC 发表于 2014-11-6 09:41
能给个详细的link或者code吗？

public void rotate(int[][] matrix) {
        //先对角线翻转一次，在沿中线翻转
        int len = matrix.length;
        for (int i = 0; i < len; i++)
            for (int j = 0; j < len - i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[len-1-j][len-1-i];
                matrix[len-1-j][len-1-i] = temp;
            }
        
        for (int i = 0; i < len / 2; i++)
            for (int j = 0; j < len; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[len-1-i][j];
                matrix[len-1-i][j] = temp;
            }
    }

行的中线。如果你有3行——0，1，2——那就是行1

是LeetCode上面那个旋转90度的题目吗？
我的方法很好理解：
旋转90度的结果跟求转置很像。区别是第一行变成最后一列而不是第一列。
所以可以先给这个矩阵转置。然后把前n/2列逐次和后n/2列交换就行了。

zombiecry 发表于 2014-11-5 21:56
是LeetCode上面那个旋转90度的题目吗？
我的方法很好理解：
旋转90度的结果跟求转置很像。区别是第一行变 ...

对，就是那道，大牛贴一下code吧

不开辟新空间能做到？ 起码也要有一个O(1)的新空间吧， swap的时候不用一个变量，怎么swap？

如果连循环时候的变量都不能设立，我也没着了。
不然，可以用异或交换两个变量，这样不用开辟额外空间。
异或交换之前，要判断当前行和列是否相等，以及值是否相等。

先沿西南到东北的对角线翻转一次，在沿垂直中线翻转一次

ysyyork 发表于 2014-11-6 01:17
先沿西南到东北的对角线翻转一次，在沿垂直中线翻转一次

能给个详细的link或者code吗？

ysyyork 发表于 2014-11-6 01:17
先沿西南到东北的对角线翻转一次，在沿垂直中线翻转一次

垂直中线是哪一条？

evensong 发表于 2014-11-6 01:03
如果连循环时候的变量都不能设立，我也没着了。
不然，可以用异或交换两个变量，这样不用开辟额外空间。
...

可以交换的，能详细点说吗