c**********e
发帖数: 2007 | 1 Suppose we have an array
a1,a2,... ,an, b1,b2,..., bn
How to change this array to
a1,b1,a2,b2, ..., an,bn in O(n) time and in O(1) space. | c**********e
发帖数: 2007 | 2 from careercup, but no answer given.
【在 c**********e 的大作中提到】
: Suppose we have an array
: a1,a2,... ,an, b1,b2,..., bn
: How to change this array to
: a1,b1,a2,b2, ..., an,bn in O(n) time and in O(1) space.
| p*****2
发帖数: 21240 | | q****x
发帖数: 7404 | 4 置换群。
【在 p*****2 的大作中提到】
: 这题以前有人问过。
| c**********e
发帖数: 2007 | 5 detail?
【在 q****x 的大作中提到】
: 置换群。
| q****x
发帖数: 7404 | 6 狗。
【在 c**********e 的大作中提到】
: detail?
| p*****2
发帖数: 21240 | | q****x
发帖数: 7404 | 8 就你了。
【在 p*****2 的大作中提到】
: 谁狗了之后给个summary呀。
| p*****2
发帖数: 21240 | | i*o
发帖数: 149 | 10 1. swap (a1, b1) to get a1,b1,a3,a4,...,an ; a2,b2,b3,...,bn
2. swap (a3, a4) with (a2, b2) => a1,b1,a2,b2, a5,a6,..., an; (a3,a4,b3,b4),
b5,b6,...bn
3. Use recursion to solve (a3,a4,b3,b4), and swap with (a5,a7,a8,a9)
Now, first 8 elements in A is done, and the first 8 elements in B
looks like (a5, a6, a7, a8, b5, b6,b7, b8);
Repeat step 3, until finished.
Complexity is O(n). | A**u
发帖数: 2458 | 11 这code 不好写吧
还有，这是o(n^2)的算法, space 也不是o(1)
),
【在 i*o 的大作中提到】
: 1. swap (a1, b1) to get a1,b1,a3,a4,...,an ; a2,b2,b3,...,bn
: 2. swap (a3, a4) with (a2, b2) => a1,b1,a2,b2, a5,a6,..., an; (a3,a4,b3,b4),
: b5,b6,...bn
: 3. Use recursion to solve (a3,a4,b3,b4), and swap with (a5,a7,a8,a9)
: Now, first 8 elements in A is done, and the first 8 elements in B
: looks like (a5, a6, a7, a8, b5, b6,b7, b8);
: Repeat step 3, until finished.
: Complexity is O(n).
| i*o
发帖数: 149 | 12 I agree codeing may not be easy.
But, I don't understand why this is O(n^2). This is clearly O(n).
Also, replacing recursion with loop is not that hard. And, that will meet
space O(1) requirement.
【在 A**u 的大作中提到】
: 这code 不好写吧
: 还有，这是o(n^2)的算法, space 也不是o(1)
:
: ),
|
|
