类似于D&C,recursively solve smaller problem, always retreat the problem as a1a2b1b2 如8个数 (a1a2)(a3a4)(b1b2)(b3b4) change to (a1a2)(b1b2)(a3a4)(b3b4) first, the easy
呼唤小尾羊吧,他以前见过那篇传说中的paper。 关键词:Inshuffle in-place linear algorithm 不过这背后有些复杂的数论知识,作为面试要求过高。一般你知道那个n*logn的方法也 就够用了。
【在 H****r 的大作中提到】 : paper link plz ... : 通过相关数论知识,直接得知每个loop的起始点偶数,这种结果在某篇paper上有介绍
r*c
16 楼
looks like O(n log n) somehow
【在 v********w 的大作中提到】 : 类似于D&C,recursively solve smaller problem, always retreat the problem as : a1a2b1b2 : 如8个数 : (a1a2)(a3a4)(b1b2)(b3b4) : change to (a1a2)(b1b2)(a3a4)(b3b4) first, the easy
r*c
17 楼
looks like O(n log n) somehow
【在 v********w 的大作中提到】 : 类似于D&C,recursively solve smaller problem, always retreat the problem as : a1a2b1b2 : 如8个数 : (a1a2)(a3a4)(b1b2)(b3b4) : change to (a1a2)(b1b2)(a3a4)(b3b4) first, the easy
b*w
18 楼
This doesn't seem to require advanced, complicated methods. One way to do so is to simply get the elements in place in the desired order . While you do this, the elements to be relocated are always in the upper part of the array. It's like the scenario in quick-sort. The trick is that the elements in A that are to be processed should be viewed as a moving, circular array which starts in the middle. Time complexity is O(n) and space complexity is O(1).