j**l
发帖数: 2911 | 1 就是把数组
A1, A2, ..., An, B1, B2, ..., Bn
变为
A1, B1, A2, B2, ..., An, Bn
要求O(n)的时间和O(1)空间
CareerCup的书上，给出了O(n^2)和O(n*logn)的两种方法。
先看两个简单例子
n = 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
A1 A2 A3 A4 A5 A6 A7 A8 B1 B2 B3 B4 B5 B6 B7 B8
A1 B1 A2 B2 A3 B3 A4 B4 A5 B5 A6 B6 A7 B7 A8 B8
代换环路有四条分支
2->3->5->9->2
4->7->13->10->4
6->11->6
8->15->14->12->8
n = 10
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10
A1 B1 A2 B2 A3 B3 A4 | s*********t
发帖数: 1663 | 2 careercup那个书上似乎有这道题
【在 j**l 的大作中提到】
: 就是把数组
: A1, A2, ..., An, B1, B2, ..., Bn
: 变为
: A1, B1, A2, B2, ..., An, Bn
: 要求O(n)的时间和O(1)空间
: CareerCup的书上，给出了O(n^2)和O(n*logn)的两种方法。
: 先看两个简单例子
: n = 8
: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
: A1 A2 A3 A4 A5 A6 A7 A8 B1 B2 B3 B4 B5 B6 B7 B8
| v********w
发帖数: 136 | 3 类似于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
【在 j**l 的大作中提到】
: 就是把数组
: A1, A2, ..., An, B1, B2, ..., Bn
: 变为
: A1, B1, A2, B2, ..., An, Bn
: 要求O(n)的时间和O(1)空间
: CareerCup的书上，给出了O(n^2)和O(n*logn)的两种方法。
: 先看两个简单例子
: n = 8
: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
: A1 A2 A3 A4 A5 A6 A7 A8 B1 B2 B3 B4 B5 B6 B7 B8
| W***i
发帖数: 9134 | | m******e
发帖数: 64 | 5
正解
【在 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
| x****r
发帖数: 99 | 6 这样做每一个组是奇数怎么办？如果是a1..a7b1..b7这样应该怎么换？
as
【在 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
| S******A
发帖数: 1002 | 7 I would suggest you to think carefully before writing and coding:
any room to improve my code?
is there any more elegant solution? | H****r
发帖数: 2801 | 8 paper link plz ...
通过相关数论知识，直接得知每个loop的起始点偶数，这种结果在某篇paper上有介绍
【在 j**l 的大作中提到】
: 就是把数组
: A1, A2, ..., An, B1, B2, ..., Bn
: 变为
: A1, B1, A2, B2, ..., An, Bn
: 要求O(n)的时间和O(1)空间
: CareerCup的书上，给出了O(n^2)和O(n*logn)的两种方法。
: 先看两个简单例子
: n = 8
: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
: A1 A2 A3 A4 A5 A6 A7 A8 B1 B2 B3 B4 B5 B6 B7 B8
| j**l
发帖数: 2911 | 9 呼唤小尾羊吧，他以前见过那篇传说中的paper。
关键词：Inshuffle in-place linear algorithm
不过这背后有些复杂的数论知识，作为面试要求过高。一般你知道那个n*logn的方法也
就够用了。
【在 H****r 的大作中提到】
: paper link plz ...
: 通过相关数论知识，直接得知每个loop的起始点偶数，这种结果在某篇paper上有介绍
| r****c
发帖数: 2585 | 10 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
发帖数: 2585 | 11 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
发帖数: 6 | 12 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).
【在 r****c 的大作中提到】
: looks like O(n log n) somehow
|
|
