G**********s
发帖数: 70 | 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 without using any space. |
G**********s
发帖数: 70 | 2 Each line represents a different step and () signifies what is being moved this step and [] is what has been moved from last step. The array itself is used as storage and two pointers (one for L and one for N) are required to determine what to move next. L means "letter line" and N is "number line" (what is moved).
A B C D 1 2 3 4
L A B C (D) 1 2 3 4 first is L, no need to move last N
N A B C (3) 1 2 [D] 4
L A B (C) 2 1 [3] D 4
N A B 1 (2) [C] 3 D 4
L A (B) 1 [2] C
【在 G**********s 的大作中提到】
: 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 without using any space.
|
g*******y
发帖数: 1930 | 3 这是啥玩意儿啊？看不懂
【在 G**********s 的大作中提到】
: Each line represents a different step and () signifies what is being moved this step and [] is what has been moved from last step. The array itself is used as storage and two pointers (one for L and one for N) are required to determine what to move next. L means "letter line" and N is "number line" (what is moved).
: A B C D 1 2 3 4
: L A B C (D) 1 2 3 4 first is L, no need to move last N
: N A B C (3) 1 2 [D] 4
: L A B (C) 2 1 [3] D 4
: N A B 1 (2) [C] 3 D 4
: L A (B) 1 [2] C
|
c*********n
发帖数: 1057 | 4 可以recursive么？
【在 G**********s 的大作中提到】
: Each line represents a different step and () signifies what is being moved this step and [] is what has been moved from last step. The array itself is used as storage and two pointers (one for L and one for N) are required to determine what to move next. L means "letter line" and N is "number line" (what is moved).
: A B C D 1 2 3 4
: L A B C (D) 1 2 3 4 first is L, no need to move last N
: N A B C (3) 1 2 [D] 4
: L A B (C) 2 1 [3] D 4
: N A B 1 (2) [C] 3 D 4
: L A (B) 1 [2] C
|
G**********s
发帖数: 70 | 5 why not..yes you can, but have to be sure constant extra space
【在 c*********n 的大作中提到】
: 可以recursive么？
|
g*******y
发帖数: 1930 | 6 你在哪儿看的，某论坛某帖子里面某个普通老美/老印的回复？直接无视之！
我是看不出他这个算法是怎么做到O(N)+O(1)的
O(n)+O(1)的解法是有人发过paper的，哪有这么轻松的。好歹也得整些数论在里面
this step and [] is what has been moved from last step. The array itself is
used as storage and two pointers (one for L and one for N) are required to
determine what to move next. L means "letter line" and N is "number line" (
what is moved).
【在 G**********s 的大作中提到】
: Each line represents a different step and () signifies what is being moved this step and [] is what has been moved from last step. The array itself is used as storage and two pointers (one for L and one for N) are required to determine what to move next. L means "letter line" and N is "number line" (what is moved).
: A B C D 1 2 3 4
: L A B C (D) 1 2 3 4 first is L, no need to move last N
: N A B C (3) 1 2 [D] 4
: L A B (C) 2 1 [3] D 4
: N A B 1 (2) [C] 3 D 4
: L A (B) 1 [2] C
|
G**********s
发帖数: 70 | 7 在网上找到的solution，
http://stackoverflow.com/questions/1777901/array-operation
http://discuss.joelonsoftware.com/default.asp?interview.11.482833.19
我也觉得没有这么轻松。那如果真遇到这题，你怎么回应呢
is
to
【在 g*******y 的大作中提到】
: 你在哪儿看的，某论坛某帖子里面某个普通老美/老印的回复？直接无视之！
: 我是看不出他这个算法是怎么做到O(N)+O(1)的
: O(n)+O(1)的解法是有人发过paper的，哪有这么轻松的。好歹也得整些数论在里面
:
: this step and [] is what has been moved from last step. The array itself is
: used as storage and two pointers (one for L and one for N) are required to
: determine what to move next. L means "letter line" and N is "number line" (
: what is moved).
|
g*******y
发帖数: 1930 | 8 我就直接说做过，看过solution是一篇paper，让他换题。
或者写个自己能想到的nlogn算法
【在 G**********s 的大作中提到】
: 在网上找到的solution，
: http://stackoverflow.com/questions/1777901/array-operation
: http://discuss.joelonsoftware.com/default.asp?interview.11.482833.19
: 我也觉得没有这么轻松。那如果真遇到这题，你怎么回应呢
:
: is
: to
|
G**********s
发帖数: 70 | 9 geniusxsy (小尾羊), 多谢你的意见。=)
【在 g*******y 的大作中提到】
: 我就直接说做过，看过solution是一篇paper，让他换题。
: 或者写个自己能想到的nlogn算法
|
r****o
发帖数: 1950 | 10 能不能说说你的那个nlogn算法，呵呵。
【在 g*******y 的大作中提到】
: 我就直接说做过，看过solution是一篇paper，让他换题。
: 或者写个自己能想到的nlogn算法
|
|
|
G**********s
发帖数: 70 | 11 divide & conquer
切一半，swap一次。。重复做
T(n) = 2T(n/2) + O(n) hence . T(n) < O(nlogn)
【在 r****o 的大作中提到】
: 能不能说说你的那个nlogn算法，呵呵。
|
s**t
发帖数: 15 | 12 It equal to change two variables without extra space.
|a|b|: a<->b
a'b'
a' = a + b
b' = a - b
a' = (a'- b') / 2 =((a + b) - (a - b)) / 2 = 2*b / 2 = b (b replaced a')
b' = (b'+ b) = a - b + b = a ( a replace b')
so |a|b| -> |b|a| |
G**********s
发帖数: 70 | 13 swapping的那个我懂，但是不懂老美怎么推每次swap的位置,问题表达不清晰，见两！ |
c*********n
发帖数: 1057 | 14 interview的时候说出nlogn的就可以了吧
【在 g*******y 的大作中提到】
: 我就直接说做过，看过solution是一篇paper，让他换题。
: 或者写个自己能想到的nlogn算法
|
c***y
发帖数: 560 | 15 sorry, what's the trick behind this divide & conquer?
more detail, thanks.
【在 G**********s 的大作中提到】
: divide & conquer
: 切一半，swap一次。。重复做
: T(n) = 2T(n/2) + O(n) hence . T(n) < O(nlogn)
|
r****o
发帖数: 1950 | 16 如果n不是2的n次方的话，好像处理起来有点小tricky。
【在 G**********s 的大作中提到】
: divide & conquer
: 切一半，swap一次。。重复做
: T(n) = 2T(n/2) + O(n) hence . T(n) < O(nlogn)
|
H*M
发帖数: 1268 | 17 填成2^n?如果不是的话，那个index要分奇偶得好像...没有统一的表示法
【在 r****o 的大作中提到】
: 如果n不是2的n次方的话，好像处理起来有点小tricky。
|
r****o
发帖数: 1950 | 18 我没想出比较好的办法。
有谁做出来了非2^n情况的O(nlogn)的算法吗？
【在 H*M 的大作中提到】
: 填成2^n?如果不是的话，那个index要分奇偶得好像...没有统一的表示法
|
r****o
发帖数: 1950 | 19 自己顶一下。
【在 r****o 的大作中提到】
: 我没想出比较好的办法。
: 有谁做出来了非2^n情况的O(nlogn)的算法吗？
|
