教えて君ですいません、非常に基本的な操作に関してなんですが、
自分の稚拙な頭じゃ思いつかないので質問いたします。

長さ N×M の配列 A があり、これが N×M の行列を表しているとします
つまり、A[i*M + j] が行列 A の(i,j)成分であると考えます。
（i=0,1,…,N-1, j=0,1,…,M-1 とします）

この行列を
"動的なメモリの確保なしに" (つまりN,Mに依存する余分な記憶領域を使わず）
転置して、M×N行列にしたいのです。
(もちろんN != M の場合に関してです。）

すなわち、Aの(i,j)成分
A(i,j) = A[i*N + j]
を、転置行列A' （Aと同じ配列です）の (j,i)成分
A'(j,i) = A[j*M + i]
としたいのです。

O(NM)の計算量でこのような操作は可能でしょうか？