数组原地交换

例1 旋转图像

分析：每四个数构成一个互相交换的环，对所有这些环交换即可。
1，外层循环控制一圈
2，内层循环遍历每个每个环的起点m[i][j]，它的三个后继可以推导出来
3，一个环的交换，这里用其他元素分别和同一元素交换实现。（顺时针旋转：其他元素按顺时针顺序和同一元素交换,逆时针同理）

void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        if(n==0) return;
        if(n!=matrix[0].size()) return;

        for(int i=0;i<=n/2;i++){ //外围圈
            for(int j=i;j<=n-2-i;j++){ //每个环的起点
                //四个数交换
                swap(matrix[n-1-j][i],matrix[i][j]);
                swap(matrix[n-1-j][i],matrix[j][n-1-i]);
                swap(matrix[n-1-j][i],matrix[n-1-i][n-1-j]);
            }
        }
        return;
    }

例2 矩阵转置

将一个m*n的矩阵存储在一个一维数组中，原地实现矩阵的转置。
分析：以一个4x2的矩阵A={1,2,3,4,5,6,7,8}进行分析。
转置前：1，2，3，4，5，6，7，8
转置后：1，3，5，7，2，4，6，8

可以看出有四个独立的交换环。

算法：遍历数组，判断该位置的环若未处理过，则对该环进行一次交换。
1，如何判断环是重复已处理过的？遍历数组时下标是从小到大的，所以如果是第一次遍历该环，则第一个下标肯定是这个环中最小的。如果一个环被处理过，那么总能找到一个它的后继是小于它的。
2，如何计算当前元素下标的前驱与后继？假设转置前某个元素的数组下标为i，则它所在行列为（i/N, i%N），转置后所在行列则为（i%N, i/N），可计算转置后数组下标为(i%N)M+i/N，此为i的后继。假设转置后某个元素的数组下标为i，则它所在行列为（i/M, i%M），则转置前所在行列为（i%M, i/M），可计算此时下标为(i%M)N+i/M，此为i的前驱。

int getnext(int i,int m,int n){
    return (i%n)*m + i/n;
}

void transpose(vector<int>& a,int m,int n){
    for(int i=0;i<a.size();i++){   //遍历数组
        int next=getnext(i,m,n);  //判断是否处理过
        while(next>i){
            next=getnext(next,m,n);
        }
        if(i==next){   //未处理过，对该环进行处理
            next=getnext(i,m,n);  
            while(next!=i){
                swap(a[i],a[next]);
                next=getnext(next,m,n);
            }
        }
    }
}