【重构】人人都来写算法 之 矩阵顺时针旋转90度，空间效率O(1)，时间效率O(n*n)

下班之前，抽了15分钟对之前的一段代码进行了重构，虽然使用指针操作二维数组在可读性上没有原来的二维下标访问清晰，但是为了消除重复也只能这样了。

原文链接：

http://blog.csdn.net/walle_love_eva/article/details/9951977

重构后的代码：

#include <iostream>
#include <iomanip>

using std::cout;
using std::endl;
using std::setw;

const int SIZE_4 = 4;
const int SIZE_7 = 7;

void printImage(int* matrix, int size)
{
    for(int i=0; i<size; ++i)
    {
        for(int j=0; j<size; ++j)
        {
            cout<<setw(4)<<matrix[i*size + j]<<" ";
        }
        cout<<endl;
    }
    cout<<"-----------------------------"<<endl;
}

void swap(int &a, int &b)
{
    if(&a == &b)
    {
        return;
    }
    int temp = a;
    a = b;
    b = temp;
}

void swap_bitOpt(int &a, int &b)
{
    if(&a == &b)
    {
        return;
    }
    a = a^b;
    b = a^b;
    a = a^b;
}

void transpose90_zero(int* matrix, int size)
{
    //Diagonal Flip
    for(int i=0; i<size; ++i)
    {
        for(int j=i+1; j< size; ++j)
        {
            swap_bitOpt(matrix[i*size + j], matrix[j*size + i]);
        }
    }

    //Flip form left to right
    for(int i=0; i<size; ++i)
    {
        for(int j=0; j<size/2; j++)
        {
            swap(matrix[i*size +j], matrix[i*size +(size-j-1)]);
        }
    } 
}

void transpose90_one(int* matrix, int size)
{
    //Flip up and down
    for(int i=0; i<size/2; ++i)
    {
        for(int j=0; j<size; j++)
        {
            swap(matrix[i*size +j], matrix[(size-i-1)*size +j]);
        }
    }
    
    //Diagonal Flip
    for(int i=0; i<size; ++i)
    {
        for(int j=i+1; j< size; ++j)
        {
            swap(matrix[i*size + j], matrix[j*size + i]);
        }
    }
}

void transpose90_two(int* matrix, int size)
{
    for(int layer=0; layer<size/2; ++layer)
    {
        int first = layer;
        int last = size-1-layer;

        for(int i=first; i<last; ++i)
        {
            int offset = i - first;
            int top = matrix[first*size + i];
            matrix[first*size + i] = matrix[(last-offset)*size + first];
            matrix[(last-offset)*size + first] = matrix[last*size +(last-offset)];
            matrix[last*size + (last-offset)] = matrix[i*size + last];
            matrix[i*size + last] = top;
        }
    }
}

void transpose90_three(int* matrix, int size)
{
    for(int layer=0; layer<size/2; ++layer)
    {
        int last = size-layer -1;
        int iter = 0;
        for(int i=layer; i<last; ++i)
        {
            int reverse_i = last - iter;
            int top = matrix[layer*size + i];
            matrix[layer*size + i] = matrix[reverse_i*size + layer];
            matrix[reverse_i*size + layer] = matrix[last*size + reverse_i];
            matrix[last*size + reverse_i] = matrix[i*size + last];
            matrix[i*size + last] = top;
            iter++;
        }
    }
}


int main()
{
    int image[SIZE_7][SIZE_7] = {
        {1,2,3,4,5,6,7}, 
        {8,9,10,11,12,13,14}, 
        {15,16,17,18,19,20,21}, 
        {22,23,24,25,26,27,28},
        {29,30,31,32,33,34,35},
        {36,37,38,39,40,41,42},
        {43,44,45,46,47,48,49}};

    //Test even matrix
    printImage((int*)image, 4);
    transpose90_zero((int*)image, 4);
    printImage((int*)image, 4);
    transpose90_one((int*)image, 4);
    printImage((int*)image, 4);
    transpose90_two((int*)image, 4);
    printImage((int*)image, 4);
    transpose90_three((int*)image, 4);
    printImage((int*)image, 4);
    
    //Test odd matrix
    printImage((int*)image, 7);
    transpose90_zero((int*)image, 7);
    printImage((int*)image, 7);
    transpose90_one((int*)image, 7);
    printImage((int*)image, 7);
    transpose90_two((int*)image, 7);
    printImage((int*)image, 7);
    transpose90_three((int*)image, 7);
    printImage((int*)image, 7);

    getchar();
}

【重构】人人都来写算法 之 矩阵顺时针旋转90度，空间效率O(1)，时间效率O(n*n),布布扣,bubuko.com

【重构】人人都来写算法 之 矩阵顺时针旋转90度，空间效率O(1)，时间效率O(n*n)

原文：http://blog.csdn.net/walle_love_eva/article/details/21028247