转置存储在一维数组中的矩阵，无需使用额外的内存 [英] Transpose matrix stored in a 1-dimensional array without using extra memory

问题描述

可能重复：

就地置换矩阵

最近参加了技术书面面试。遇到了以下问题。

我有一个数组，例如

  testArray = {a1，a2，a3，... an，b1，b2，b3，.... bn，c1，c2，c3，.....，cn} 
  

我需要将此数组排序为`

  testArray = {a1，b1，c1，a2，b2，c2，a3，b3，c3，.....，an，bn，cn} 
  

约束是我不应该使用额外的内存，也不应该使用任何内置函数。
应该编写完整的代码，可以使用任何语言，也可以使用任何数据结构。

例如：

 输入：{1,2,3,4,5,6,7,8,9}，n = 3 
 
输出：{ 1,4,7,2,5,8,3,6,9} 
  

我无法得到约束内的任何解决方案，有人可以提供解决方案或建议吗？

解决方案

这只是矩阵转置操作。甚至在Wikipedia上就地矩阵转置都存在问题和解决方案。 p>

没有多余的空间是不可能的，因为您至少需要遍历数组。 O（1）可能会增加内存，但时间复杂度会受到严重影响。

该解决方案基于Wikipedia页面中的循环跟踪算法：对于每个单元格，我们将找到循环中索引最小的单元格。如果具有最小索引的单元格大于或等于（> =）当前单元格的索引，我们将执行链交换。否则，我们将忽略该单元格，因为它已正确交换。 （经过松散分析的）时间复杂度的上限可能高达O（（MN） ² ）（我们经过M * N个单元，周期只能与总数相等单元格。）

Possible Duplicate:
In-place transposition of a matrix

Recently attended an Technical Written Interview. Came through the following question.

I have an array as say

testArray = {a1,a2,a3,...an,b1,b2,b3,....bn,c1,c2,c3,.....,cn}

I need to sort this array as `

testArray = {a1,b1,c1,a2,b2,c2,a3,b3,c3,.....,an,bn,cn}

Constraint is I should not use extra memory, should not use any inbuilt function. Should write complete code, it can be in any language and can also use any data structure.

eg:

Input: {1,2,3,4,5,6,7,8,9}, n = 3

Output: {1,4,7,2,5,8,3,6,9}

I could not get any solution within the constraint, can anyone provide solution or suggestion?

解决方案

This is just a matrix transpose operation. And there is even a problem and solution for in-place matrix transposition on Wikipedia.

No extra space is impossible, since you need to at least go through the array. O(1) additional memory is possible, with heavy penalty on the time complexity.

The solution is built on follow-the-cycle algorithm in the Wikipedia page: for each cell, we will find the cell with the smallest index in the cycle. If the cell with the smallest index is greater than or equal (>=) to the index of the current cell, we will perform chain swapping. Otherwise, we ignore the cell, since it has been swapped correctly. The (loosely analyzed) upper bound on time complexity can go as high as O((MN)²) (we go through M * N cells, and the cycle can only be as long as the total number of cells).

这篇关于转置存储在一维数组中的矩阵，无需使用额外的内存的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！