C++實現(xiàn)矩陣原地轉(zhuǎn)置算法
本文實例描述了C++實現(xiàn)矩陣原地轉(zhuǎn)置算法,是一個非常經(jīng)典的算法,相信對于學(xué)習(xí)C++算法的朋友有很大的幫助。具體如下:
一、問題描述
微軟面試題:將一個MxN的矩陣存儲在一個一維數(shù)組中,編程實現(xiàn)矩陣的轉(zhuǎn)置。
要求:空間復(fù)雜度為O(1)
二、思路分析
下面以一個4x2的矩陣A={1,2,3,4,5,6,7,8}進行分析,轉(zhuǎn)置過程如下圖:
圖中右下角的紅色數(shù)字表示在一維數(shù)組中的下標(biāo)。矩陣的轉(zhuǎn)置其實就是數(shù)組中元素的移動,具體的移動過程如下圖:
我們發(fā)現(xiàn),這些移動的元素的下標(biāo)是一個個環(huán),下標(biāo)1的元素移動到4,下標(biāo)4的元素移動到2,下標(biāo)2的元素移動到1。在編寫程序的時候,我們需要解決兩個問題:第一個是如何判定環(huán)是否重復(fù)(已處理過);第二個是如何計算當(dāng)前元素下標(biāo)的前驅(qū)與后繼。
第一個問題:如何判斷環(huán)是重復(fù)已處理過的?因為我們遍歷整個數(shù)組時下標(biāo)是從小到大的,所以如果是第一次遍歷該環(huán),則第一個下標(biāo)肯定是這個環(huán)中最小的。如果一個環(huán)被處理過,那么總能找到一個它的后繼是小于它的。從上圖可以明顯看出來。
第二個問題:如何計算當(dāng)前元素下標(biāo)的前驅(qū)與后繼?假設(shè)轉(zhuǎn)置前某個元素的數(shù)組下標(biāo)為i,則它所在行列為(i/N, i%N),轉(zhuǎn)置后所在行列則為(i%N, i/N),可計算轉(zhuǎn)置后數(shù)組下標(biāo)為(i%N)*M+i/N,此為i的后繼。假設(shè)轉(zhuǎn)置后某個元素的數(shù)組下標(biāo)為i,則它所在行列為(i/M, i%M),則轉(zhuǎn)置前所在行列為(i%M, i/M),可計算此時下標(biāo)為(i%M)*N+i/M,此為i的前驅(qū)。
三、代碼實現(xiàn)如下:
/************************************************************************* > 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; } /* 前驅(qū) */ int getPre(int i, int m, int n) { return (i%m)*n + i/m; } /* 處理以下標(biāo)i為起點的環(huán) */ void movedata(int *mtx, int i, int m, int n) { int temp = mtx[i]; // 暫存 int cur = i; // 當(dāng)前下標(biāo) int pre = getPre(cur, m, n); while(pre != i) { mtx[cur] = mtx[pre]; cur = pre; pre = getPre(cur, m, n); } mtx[cur] = temp; } /* 轉(zhuǎn)置,即循環(huán)處理所有環(huán) */ 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說明重復(fù) next = getNext(next, m, n); if(next == i) // 處理當(dāng)前環(huán) 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; }
運行結(jié)果如下圖所示:
相關(guān)文章
Visual Studio 2019配置qt開發(fā)環(huán)境的搭建過程
這篇文章主要介紹了Visual Studio 2019配置qt開發(fā)環(huán)境的搭建過程,本文圖文并茂給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-03-03C++ sdl實現(xiàn)渲染旋轉(zhuǎn)視頻的方法分享
一般情況下播放視頻時不需要旋轉(zhuǎn),但是如果是移動端錄制的視頻有時會出現(xiàn)rotate參數(shù),且視頻寬高也是互換的。所以本文為大家準(zhǔn)備了利用sdl實現(xiàn)渲染旋轉(zhuǎn)視頻的方法,需要的可以參考一下2022-12-12