矩阵就地转置＋O(Nlog(N))时间复杂度

题目信息：给定一个m*n的矩阵，将其存在在一维数组中，现在将其就地转置即空间复杂度为O(1)，并且时间复杂度限制为O(Nlog(N))

思路：以一个栗子分析如何移动数组。

比如2*5的数组为：

0 1 2 3 4
5 6 7 8 9

则其在一维数组中的形式为

0 1 2 3 4 5 6 7 8 9

而我们需要将其转置为

在一维数组中形式即为

0 5 1 6 2 7 3 8 4 9

在我们将某一位数A移动到其转置到的位置B，然后我们需要先把B移动到其转置后的位置C，这样一系列的移动就会形成一个环.其各个环如下：

0 -> 0

1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1

3 -> 6 -> 3

9 -> 9

恩，到这里我们已经完成了很重要的一步，下面我们就是需要在每一次进入一个新的环的时候，将环里的元素移动到其各自位置。当再次从环的另一个位置进入的时候，我们需要跳过这个元素。如何判断当前的环是否被处理过呢？我们可以看到，因为是在第一次进入环的时候进行对环中元素进行移位，因此当前元素的位置必然是环中最小，当再次进入环的时候，必然会存在至少一个元素位置比当前元素位置低。也就是当我们遍历到位置１的时候，我们进入一个新的环，将这个环中的所有元素移位，然后遍历的２的时候我们判断发现包含位置２的环中有位置１，所以位置２已经被移位了，就将跳过。

然后分析如何求出一个位置的后继：以index位置为例，其在二维矩阵中的坐标应该是(index/n, index%n)，转置之后x和y坐标互换，在矩阵中的位置为(index%n, index/n)。转置之后的矩阵由m*n变为n*m，所以转置之后的坐标在一维数组中的位置为((index%n)*m + index/n)。同理可以求前驱。

一般的矩阵就地转置算法就是这样了，其时间复杂度很明显可以看出是O(N^2)，我看到了一些论文有借助开少量辅助内存时间复杂度达到O(N*log(N))的，但是其在最坏情况下依然需要O(N)辅助内存。

而实际上我们可以借助一种"domination Radius"技术实现真正的就地转置并且平摊时间复杂度为O(N*log(N))的目标。这种方式其实就是在我们判断环的时候原来是从一个方向遍历环，而现在我们向两个方向同时遍历环，在最坏情况下就是两个方向的指针在相遇在某个位置或者越过彼此，但是在大部分情况下只需要走很少的步就可以结束。

代码如下：

/*************************************************************************
> File Name: trans.cpp
> Author: Jonah
> Mail: mren@g.clemson.edu
> Created Time: Wed 27 Jan 2016 09:14:47 PM EST
 ************************************************************************/

#include<iostream>
#include<vector>
using namespace std;

inline int prePos(int m, int n, int index)
{   //找到前驱
    return (index%m)*n + index/m; 
}

inline int nextPos(int m, int n, int index)
{　　//找到后继
    return (index%n)*m + index/n;
}

void trans(vector<int>& matrix, int m, int n)
{
    int len = matrix.size();
    for(int i = 0; i< len; i++)
    {
        int pre = prePos(m,n,i), next = nextPos(m,n,i); 
        //指针向两方向同时移动
        while(pre > i && next > i && pre!= next && prePos(m, n, pre) != next) 
        {
            pre = prePos(m,n,pre);
            next = nextPos(m,n,next); 
        }
        if(pre < i || next < i)//此环已被处理过
            continue;
        int cur =i, val = matrix[i];
        pre = prePos(m, n, cur);
        while(pre != i)//移动环中的元素
        {
            matrix[cur] = matrix[pre];
            cur = pre;
            pre = prePos(m, n, cur);
        }
        matrix[cur] = val;
    } 
}
int main()
{
    vector<int> vec;
    int m = 2, n = 5;
    for(int i = 0; i< 10; i++)
       vec.push_back(i);
    for(int i = 0; i< m; i++)//输出矩阵转置之前的值
    {
        for(int j = 0; j< n; j++)
            cout << vec[i*n+j] << " ";
        cout << endl;
    }
    cout << endl;
    trans(vec, m, n); 
    for(int i = 0; i< n; i++)//输出矩阵转置之后的值
    {
        for(int j = 0; j< m; j++)
            cout << vec[i*m+j] << " ";
        cout << endl;
    }

    return 0;
}

秒客网

矩阵就地转置＋O(Nlog(N))时间复杂度

相关文章