原位（固定空間）M x N 大小的矩陣轉置| 更新 · GeeksForGeeks 中文系列教程

# 原位（固定空間）M x N 大小的矩陣轉置| 更新 > 原文： [https://www.geeksforgeeks.org/inplace-m-x-n-size-matrix-transpose/](https://www.geeksforgeeks.org/inplace-m-x-n-size-matrix-transpose/) 一個新職位大約有四個月的缺口（缺少 GFG）。給定一個 M x N 矩陣，請在不使用輔助存儲器的情況下轉置該矩陣。使用輔助數組很容易轉置矩陣。如果矩陣大小對稱，我們可以通過在二維對角線上鏡像二維數組來對矩陣進行原位轉置（嘗試一下）。如何在適當位置轉置任意大小的矩陣？參見下面的矩陣， ``` a b c a d g j d e f ==> b e h k g h i c f i l j k l ``` 根據 C/C++ 中的 2D 編號，相應的位置映射如下所示： ``` Org element New 0 a 0 1 b 4 2 c 8 3 d 1 4 e 5 5 f 9 6 g 2 7 h 6 8 i 10 9 j 3 10 k 7 11 l 11 ``` 請注意，第一個和最后一個元素保留在其原始位置。我們可以很容易地看到變換形成了很少的排列周期。 * 1- > 4- > 5- > 9- > 3- > 1 ―總共 5 個元素組成一個循環 * 2- > 8- > 10- > 7- > 6- > 2 –循環中還有 5 個元素 * 0 –自循環 * 11 –自循環從上面的示例中，我們可以輕松設計一種算法來沿著這些循環移動元素。 *如何生成置換周期？* 這兩個矩陣中的元素數是恒定的，由 N = R * C 給出，其中 R 是行數，C 是列數。位置*或*（R x C 矩陣中的舊位置）的元素移至 *nl* （C x R 矩陣中的新位置）。我們需要建立 *ol，nl，R* 和 *C* 之間的關系。假設 *ol ＝ A [或] [oc]* 。在 C/C++ 中，我們可以將元素地址計算為 ``` ol = or x C + oc (ignore base reference for simplicity) ``` 它應移至轉置矩陣中的新位置 *nl* ，例如 *nl = A [nr] [nc]* 或 C/C++ 術語 ``` nl = nr x R + nc (R - column count, C is row count as the matrix is transposed) ``` 觀察 *nr = oc* 和 *nc =或*，因此將其替換為 *nl* ， ``` nl = oc x R + or -----> [eq 1] ``` 解決 *ol* 和 *nl* 之間的關系后，我們得到 ``` ol = or x C + oc ol x R = or x C x R + oc x R = or x N + oc x R (from the fact R * C = N) = or x N + (nl - or) --- from [eq 1] = or x (N-1) + nl ``` 要么， ``` nl = ol x R - or x (N-1) ``` 請注意， *nl* 和 *ol* 的值永遠不會超出 *N-1* ，因此請考慮在兩側進行模除以（ *N-1* ），我們根據同余性得到以下結果： ``` nl mod (N-1) = (ol x R - or x (N-1)) mod (N-1) = (ol x R) mod (N-1) - or x (N-1) mod(N-1) = ol x R mod (N-1), since second term evaluates to zero nl = (ol x R) mod (N-1), since *nl* is always less than *N-1* ``` **好奇的讀者可能已經注意到上述關系的重要性。每個位置的縮放比例為 R（行大小）。從矩陣中可以明顯看出，每個位置都由 R 的比例因子位移。實際的乘數取決于（N-1）的同余類，即乘數可以是同等類的-ve 和+ ve 值。** 因此，每個位置變換都是簡單的模除法。這些模除法形成循環排列。我們需要一些簿記信息來跟蹤已經移動的元素。這是就地矩陣轉換的代碼， ``` // Program for in-place matrix transpose #include <stdio.h> #include <iostream> #include <bitset> #define HASH_SIZE 128 using namespace std; // A utility function to print a 2D array of size nr x nc and base address A void Print2DArray(int *A, int nr, int nc) { ????for(int r = 0; r < nr; r++) ????{ ????????for(int c = 0; c < nc; c++) ????????????printf("%4d", *(A + r*nc + c)); ????????printf("\n"); ????} ????printf("\n\n"); } // Non-square matrix transpose of matrix of size r x c and base address A void MatrixInplaceTranspose(int *A, int r, int c) { ????int size = r*c - 1; ????int t; // holds element to be replaced, eventually becomes next element to move ????int next; // location of 't' to be moved ????int cycleBegin; // holds start of cycle ????int i; // iterator ????bitset<HASH_SIZE> b; // hash to mark moved elements ????b.reset(); ????b[0] = b[size] = 1; ????i = 1; // Note that A[0] and A[size-1] won't move ????while (i < size) ????{ ????????cycleBegin = i; ????????t = A[i]; ????????do ????????{ ????????????// Input matrix [r x c] ????????????// Output matrix ????????????// i_new = (i*r)%(N-1) ????????????next = (i*r)%size; ????????????swap(A[next], t); ????????????b[i] = 1; ????????????i = next; ????????} ????????while (i != cycleBegin); ????????// Get Next Move (what about querying random location?) ????????for (i = 1; i < size && b[i]; i++) ????????????; ????????cout << endl; ????} } // Driver program to test above function int main(void) { ????int r = 5, c = 6; ????int size = r*c; ????int *A = new int[size]; ????for(int i = 0; i < size; i++) ????????A[i] = i+1; ????Print2DArray(A, r, c); ????MatrixInplaceTranspose(A, r, c); ????Print2DArray(A, c, r); ????delete[] A; ????return 0; } ``` 輸出： ``` 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 1 7 13 19 25 2 8 14 20 26 3 9 15 21 27 4 10 16 22 28 5 11 17 23 29 6 12 18 24 30 ``` **擴展名：2013 年 3 月 17 日–** 一些[閱讀器](https://www.geeksforgeeks.org/inplace-m-x-n-size-matrix-transpose/#comment-15647)確定了矩陣轉置和[字符串轉換](https://www.geeksforgeeks.org/an-in-place-algorithm-for-string-transformation/)之間的相似性。沒有太多理論，我提出了問題和解決方案。在給定的元素數組中，例如[a1b2c3d4e5f6g7h8i9j1k2l3m4]。將其轉換為[abcdefghijklm1234567891234]。該程序應在原地運行。我們需要的是原位轉置。下面給出的是代碼。 ``` #include <stdio.h> #include <iostream> #include <bitset> #define HASH_SIZE 128 using namespace std; typedef char data_t; void Print2DArray(char A[], int nr, int nc) { ???int size = nr*nc; ???for(int i = 0; i < size; i++) ??????printf("%4c", *(A + i)); ???printf("\n"); } void MatrixTransposeInplaceArrangement(data_t A[], int r, int c) { ???int size = r*c - 1; ???data_t t; // holds element to be replaced, eventually becomes next element to move ???int next; // location of 't' to be moved ???int cycleBegin; // holds start of cycle ???int i; // iterator ???bitset<HASH_SIZE> b; // hash to mark moved elements ???b.reset(); ???b[0] = b[size] = 1; ???i = 1; // Note that A[0] and A[size-1] won't move ???while( i < size ) { ??????cycleBegin = i; ??????t = A[i]; ??????do { ?????????// Input matrix [r x c] ?????????// Output matrix ?????????// i_new = (i*r)%size ?????????next = (i*r)%size; ?????????swap(A[next], t); ?????????b[i] = 1; ?????????i = next; ??????} while( i != cycleBegin ); ??????// Get Next Move (what about querying random location?) ??????for(i = 1; i < size && b[i]; i++) ?????????; ??????cout << endl; ???} } void Fill(data_t buf[], int size) { ???// Fill abcd ... ???for(int i = 0; i < size; i++) ???buf[i] = 'a'+i; ???// Fill 0123 ... ???buf += size; ???for(int i = 0; i < size; i++) ??????buf[i] = '0'+i; } void TestCase_01(void) { ???int r = 2, c = 10; ???int size = r*c; ???data_t *A = new data_t[size]; ???Fill(A, c); ???Print2DArray(A, r, c), cout << endl; ???MatrixTransposeInplaceArrangement(A, r, c); ???Print2DArray(A, c, r), cout << endl; ???delete[] A; } int main() { ???TestCase_01(); ???return 0; } ``` ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ **2016 年 7 月 9 日更新：有關空間復雜性和存儲順序的說明。** 很長一段時間后，碰巧要審查此帖子。當我們使用位集作為標記（代碼中的*哈希*）時，一些讀者提出了一些有效的問題，關于它如何就位（？）。通過查看標題或內容來對錯誤的理解表示歉意。在準備初始內容時，我正在考慮使用至少需要轉置矩形矩陣的 O（MN）輔助空間來實現樸素的實現。上面顯示的程序使用恒定空間，因為位集大小在編譯時是固定的。但是，為了支持矩陣的任意大小，我們需要位集大小至少為 O（MN）大小。可以使用 HashMap（攤銷的 *`O(1)`*復雜度）標記完成的位置，但 HashMap 最壞的情況是 *`O(n)`*或 *`O(log n)`* 基于實現。 HashMap 的空間成本也會根據插入的項目而增加。 *請注意，原位使用。矩陣空間* 同樣，假設矩陣將以行主要順序（存儲器中的連續位置）存儲。如果矩陣是用編程語言（例如 Fortran / Julia）以列的主要順序表示的，則讀者可以得出公式。感謝那些指出了這兩個空白的讀者。 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 該帖子不完整，沒有提及兩個鏈接。 1\. Aashish 在循環前導算法后面介紹了很好的理論。請參閱他關于[字符串轉換](https://www.geeksforgeeks.org/an-in-place-algorithm-for-string-transformation/)的文章。 2\. [Sambasiva](http://effprog.wordpress.com) 像往常一樣展示了他在[問題](http://effprog.wordpress.com/2010/08/02/in-a-given-array-of-elements-like-a1-a2-a3-a4-an-b1-b2-b3-b4-bn-c1-c2-c3-c4-cn-without-taking-a-extra-memory-how-to-merge-like-a1-b1-c1-a2-b2-c2-a3-b3-c/)遞歸上的非凡技巧。確保了解他的解決方案。 - [Venki](http://www.linkedin.com/in/ramanawithu) 。如果發現任何不正確的地方，或者想分享有關上述主題的更多信息，請寫評論。