原位（固定空间）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) 。如果发现任何不正确的地方，或者想分享有关上述主题的更多信息，请写评论。