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

daihao0310 发表于 2014-11-5 23:14
建议楼主可以看一下Cracking the Code Interview这本书，上面对这道题有比较详细的算法描述。

哥，我看了那个解法，太复杂了根本不好理解啊

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

MTC 发表于 2014-11-6 09:54
可以交换的，能详细点说吗

if (a !＝ b)
        a ^＝ b, b^＝a, a^＝b;

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

    void rotate(vector<vector<int> > &matrix) {
        int n=matrix.size();
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                swap(matrix[j],matrix[j][i]);
            }
        }
        for(int j=0;j<n/2;j++){
            for(int i=0;i<n;i++){
                swap(matrix[i][j],matrix[i][n-1-j]);
            }
        }
    }
[/i][/i][/i]如果O(1)空间都不能开辟的话，就用位运算代替swap吧，具体可以搜一下。

来个python的

class Solution:
    # @param matrix, a list of lists of integers
    # @return a list of lists of integers
    def rotate(self, matrix):
        l = len(matrix)
        for i in xrange(0, l - 1):
            for j in xrange(l - 1 - i):
                matrix[j], matrix[l-1-j][l-1-i] = matrix[l-1-j][l-1-i], matrix[i][j]
        i, j = 0, l - 1
        while i < j:
            matrix[i], matrix[j] = matrix[j], matrix[i]
            i, j = i + 1, j - 1
        return matrix[/i][/i][/i]

补充内容 (2014-11-7 12:13):
沿dediag转置，交换行（比换列快很多）

给个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;
}

想到一个也许可行的吧，因为是N*N，可研主对角线分成两部分，假设上半部分是Aij，下半部分是Aji，首先上半部分减下半部分，上半部分变成Aij-Aji，下半部分保留；下半部分与上半部分相加，上半部分保留Aij-Aji，下半部分变为Aji+(Aij-Aji)=Aij；上半部分取相反数并且与下半部分相加，上半部分变为Aji，得到转置。

双尾怪手 发表于 2014-11-7 22:44
想到一个也许可行的吧，因为是N*N，可研主对角线分成两部分，假设上半部分是Aij，下半部分是Aji，首先上半 ...

转置以后可以交换列就得到旋转的结果了？

双尾怪手 发表于 2014-11-7 22:44
想到一个也许可行的吧，因为是N*N，可研主对角线分成两部分，假设上半部分是Aij，下半部分是Aji，首先上半 ...

转置以后可以交换列就得到旋转的结果了

kelvinzhong 发表于 2014-11-6 00:38
不开辟新空间能做到？ 起码也要有一个O(1)的新空间吧， swap的时候不用一个变量，怎么swap？

可以用xor实现in place的swap
int a = 6, b = 8;
a = a ^ b;
b = a ^ b;
a = a ^ b;
这样a＝8，b＝6了