我连对象都没有 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

我连对象都没有

我连对象都没有# Joke - 肚皮舞运动

c*e2011-09-12 07:09

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.

e*d2011-09-12 07:09

2 楼

当初买这房子时，对面邻居种有一排松树，后院虽小，还挺PRIVATE的。
可是现在对面房子卖了，新房主要扩建DECK，建完DECK就没有YARD了（基本靠近边界了
）。我家仅有的一点后院等于两家SHARE了。去问过TOWNSHIP，回答只要不越边界，我
们没法阻止他们。这种情况该怎么办？真的只能听之任之吗？

x*s2011-09-12 07:09

3 楼

两个黄鹂鸣翠柳，我连对象都没有！
雌雄双兔奔地走，我连对象都没有！
我劝天公重抖擞，我连对象都没有！
垂死病中惊坐起，我连对象都没有！
路见不平一声吼，我连对象都没有！
问君能有几多愁，我连对象都没有！
洛阳亲友如相问，我连对象都没有！
此曲只应天上有，我连对象都没有

c*e2011-09-12 07:09

4 楼

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.

e*d2011-09-12 07:09

5 楼

说的不够清楚，那排松树已经被新房主砍了。
大家没有好主意吗？
谢谢

c*o2011-09-12 07:09

6 楼

最新的名句应该是：
“意外怀孕怎么办，我连对象都没有！”

【在 x**********s 的大作中提到】

: 两个黄鹂鸣翠柳，我连对象都没有！
: 雌雄双兔奔地走，我连对象都没有！
: 我劝天公重抖擞，我连对象都没有！
: 垂死病中惊坐起，我连对象都没有！
: 路见不平一声吼，我连对象都没有！
: 问君能有几多愁，我连对象都没有！
: 洛阳亲友如相问，我连对象都没有！
: 此曲只应天上有，我连对象都没有

p*22011-09-12 07:09

7 楼

这题以前有人问过。

d*82011-09-12 07:09

8 楼

安栅栏，或者种一排松树

z*c2011-09-12 07:09

9 楼

显然是顺序错了。应该是：
我连对象都没有，意外怀孕怎么办？

【在 c*******o 的大作中提到】

: 最新的名句应该是：
: “意外怀孕怎么办，我连对象都没有！”

q*x2011-09-12 07:09

10 楼

置换群。

【在 p*****2 的大作中提到】

: 这题以前有人问过。

B*n2011-09-12 07:09

11 楼

对啊，你自己种一排好了，你真没法要求邻居在人自家后院干什么，不干什么。

【在 d*******8 的大作中提到】

: 安栅栏，或者种一排松树

p*t2011-09-12 07:09

12 楼

倒装

【在 z**c 的大作中提到】

: 显然是顺序错了。应该是：
: 我连对象都没有，意外怀孕怎么办？

c*e2011-09-12 07:09

13 楼

detail?

【在 q****x 的大作中提到】

: 置换群。

q*x2011-09-12 07:09

14 楼

狗。

【在 c**********e 的大作中提到】

: detail?

p*22011-09-12 07:09

15 楼

谁狗了之后给个summary呀。

q*x2011-09-12 07:09

16 楼

就你了。

【在 p*****2 的大作中提到】

: 谁狗了之后给个summary呀。

p*22011-09-12 07:09

17 楼

http://zhiqiang.org/blog/science/computer-science/an-algorithm-

i*o2011-09-12 07:09

18 楼

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*u2011-09-12 07:09

19 楼

这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*o2011-09-12 07:09

20 楼

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)
:
: ),