矩阵原地转置

发表于   |   分类于   |  

问题描述

微软面试题：将一个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的前驱。

代码实现

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/*************************************************************************
    > File Name: matrix_transpose.cpp
    > Author: SongLee
    > E-mail: lisong.shine@qq.com
    > Created Time: 2014年06月06日 星期五 14时26分15秒
    > Personal Blog: http://songlee24.github.io
 ************************************************************************/
#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;
}

运行结果：