转置存储在一维数组中的矩阵,无需使用额外的内存

Question

可能重复:
矩阵的就地转置

最近参加了技术性书面访谈.通过以下问题得出结论.

我有一个阵列说

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}

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

例如:

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

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

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

Answer 1

这只是一个矩阵转置操作.维基百科上的就地矩阵转置甚至存在问题和解决方案.

没有额外的空间是不可能的,因为你需要至少通过阵列.O(1)额外的内存是可能的,严重的时间复杂性.

该解决方案基于维基百科页面中的跟随循环算法:对于每个单元格,我们将找到循环中索引最小的单元格.如果索引最小的单元格大于或等于(> =)当前单元格的索引,我们将执行链式交换.否则,我们忽略该单元格,因为它已被正确交换.(松散分析的)时间复杂度的上限可以高达O((MN)²)(我们通过M*N个单元,并且循环只能与单元的总数一样长).