本文實例描述了C++實現矩陣原地轉置算法，是一個非常經典的算法，相信對于學習C++算法的朋友有很大的幫助。具體如下：
一、問題描述
微軟面試題：將一個MxN的矩陣存儲在一個一維數組中，編程實現矩陣的轉置。
要求：空間復雜度為O(1)
二、思路分析
下面以一個4x2的矩陣A={1,2,3,4,5,6,7,8}進行分析，轉置過程如下圖：
圖中右下角的紅色數字表示在一維數組中的下標。矩陣的轉置其實就是數組中元素的移動，具體的移動過程如下圖：
我們發現，這些移動的元素的下標是一個個環，下標1的元素移動到4，下標4的元素移動到2，下標2的元素移動到1。在編寫程序的時候，我們需要解決兩個問題：第一個是如何判定環是否重復（已處理過）；第二個是如何計算當前元素下標的前驅與后繼。
第一個問題：如何判斷環是重復已處理過的？因為我們遍歷整個數組時下標是從小到大的，所以如果是第一次遍歷該環，則第一個下標肯定是這個環中最小的。如果一個環被處理過，那么總能找到一個它的后繼是小于它的。從上圖可以明顯看出來。
第二個問題：如何計算當前元素下標的前驅與后繼？假設轉置前某個元素的數組下標為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的前驅。
三、代碼實現如下：
/************************************************************************* > File Name: matrix_transpose.cpp > Author: SongLee ************************************************************************/ #include<iostream> using namespace std; /* 后繼 */ int getNext(int i, int m, int n) { return (i%n)*m + i/n; } /* 前驅 */ int getPre(int i, int m, int n) { return (i%m)*n + i/m; } /* 處理以下標i為起點的環 */ void movedata(int *mtx, int i, int m, int n) { int temp = mtx[i]; // 暫存 int cur = i; // 當前下標 int pre = getPre(cur, m, n); while(pre != i) { mtx[cur] = mtx[pre]; cur = pre; pre = getPre(cur, m, n); } mtx[cur] = temp; } /* 轉置，即循環處理所有環 */ void transpose(int *mtx, int m, int n) { for(int i=0; i<m*n; ++i) { int next = getNext(i, m, n); while(next > i) // 若存在后繼小于i說明重復 next = getNext(next, m, n); if(next == i) // 處理當前環 movedata(mtx, i, m, n); } } /* 輸出矩陣 */ void print(int *mtx, int m, int n) { for(int i=0; i<m*n; ++i) { if((i+1)%n == 0) cout << mtx[i] << "/n"; else cout << mtx[i] << " "; } } /* 測試 */ int main() { int matrix[4*2] = {1,2,3,4,5,6,7,8}; cout << "Before matrix transposition:" << endl; print(matrix, 4, 2); transpose(matrix, 4, 2); cout << "After matrix transposition:" << endl; print(matrix, 2, 4); return 0; } 運行結果如下圖所示：
新聞熱點
疑難解答
圖片精選
