C++ 矩阵转置的问题

Question

matrix t = *this;
for (size_t i = 0; i < theRows; ++i)
{
    for (size_t j = i + 1; j < theColumns; ++j)
        std::swap(t.first[i*theColumns + j], t.first[j*theColumns + i]);
}
return t;

我这个只能转置行列一样的矩阵，要怎么改进才能转置行列不一样的矩阵？？？

Answer 1

转置方阵之所以能这样写，是因为在转置过程中位置依赖所构成的环的长度小于等于2。

而对于非方阵来说，环的长度可能大于2。这个环可以根据(i, j)到数组下标的函数及数组下标到(i, j)的函数进行计算。要原地转置，只要对所有的环进行一次rotate_right即可。
如转置
1 2 3
4 5 6
元素(0, 1)在转置时位置移动所构成的环为：
(0, 1) -> (0, 2) -> (1, 1) -> (1, 0) -> (0, 1)

注意，不能简单的算出每个元素对应的环然后rotate_right，因为不同的元素可能对应相同的环，如元素(0, 1)和(0, 2)。

若在一些细节上处理到位，这个算法与非原地算法的时间复杂度相同。但是解决环重复的问题需要O(m*n)的空间。