请教一下在psoriasis 领域的大牛有哪些# Biology - 生物学
l*r
1 楼
{1，5， -5， -8，2， -1，15 }
要把负的扫到左边，正的扫到后边。
不能改变顺序
得到{-5 -8 -1 1 5 2 15}
这个题有time 低于 n^2 space=O（1）的解法吗
要把负的扫到左边，正的扫到后边。
不能改变顺序
得到{-5 -8 -1 1 5 2 15}
这个题有time 低于 n^2 space=O（1）的解法吗
y*n
2 楼
父母B2探亲，看样子是入境时边境官员忘了盖，大家遇到过这种情况吗？
a*w
4 楼
听说ergotron的不错，但是哪款便宜量又足阿。挂24寸显示器的。
e*s
5 楼
最近要做一个psoriasis 方面的project，对这个领域不是很熟悉
想请教一下这方面的大牛有哪些。 下面这几位怎么样？
UMichigan的James T. Elder
Rockefeller的James G. Krueger
Tufts的Alice Bendix Gottlieb
想请教一下这方面的大牛有哪些。 下面这几位怎么样？
UMichigan的James T. Elder
Rockefeller的James G. Krueger
Tufts的Alice Bendix Gottlieb
k*k
6 楼
in-place stable merge sort?
i may be wrong....
i may be wrong....
a*n
7 楼
找机场的CBP补盖一下
【在 y********n 的大作中提到】
: 父母B2探亲，看样子是入境时边境官员忘了盖，大家遇到过这种情况吗？
【在 y********n 的大作中提到】
: 父母B2探亲，看样子是入境时边境官员忘了盖，大家遇到过这种情况吗？
B*e
8 楼
sprint 和verizon 要lock gsm sim 的话能锁到谁家的？
【在 d*****g 的大作中提到】
: http://www.tipb.com/2011/10/12/sprint-verizon-offer-iphone-4s-u
【在 d*****g 的大作中提到】
: http://www.tipb.com/2011/10/12/sprint-verizon-offer-iphone-4s-u
s*1
9 楼
如果显示器数目超过6个以上，
到中国城，拿几张免费报纸，找到做厨柜的装修公司
打电话问他们自己有一个定制的家具，看看他们能不能做
其实牌子货都overpriced，还是上meritline买
【在 a*****w 的大作中提到】
: 听说ergotron的不错，但是哪款便宜量又足阿。挂24寸显示器的。
到中国城，拿几张免费报纸，找到做厨柜的装修公司
打电话问他们自己有一个定制的家具，看看他们能不能做
其实牌子货都overpriced，还是上meritline买
【在 a*****w 的大作中提到】
: 听说ergotron的不错，但是哪款便宜量又足阿。挂24寸显示器的。
g*y
10 楼
分冶可以做到O(nlogn)
对left right半截分别解决子问题，然后得到:
{neg_left},{pos_left} | {neg_right},{pos_right}
再把{pos_left}跟{neg_right}调换位置就行了(就是个简单的数组rotate)
对left right半截分别解决子问题，然后得到:
{neg_left},{pos_left} | {neg_right},{pos_right}
再把{pos_left}跟{neg_right}调换位置就行了(就是个简单的数组rotate)
y*n
11 楼
人已经回国了，不知如何补盖？会不会对下次签证造成影响呢，因为现在护照页上只有
中国出入境记录，没有相应的美国的出入境记录。
【在 a*****n 的大作中提到】
: 找机场的CBP补盖一下
中国出入境记录，没有相应的美国的出入境记录。
【在 a*****n 的大作中提到】
: 找机场的CBP补盖一下
j*i
12 楼
可以锁他们的international partner。比如VZW可以锁沃达丰。
【在 B*******e 的大作中提到】
: sprint 和verizon 要lock gsm sim 的话能锁到谁家的？
【在 B*******e 的大作中提到】
: sprint 和verizon 要lock gsm sim 的话能锁到谁家的？
a*w
13 楼
就一个dell 2408wfp,自用的
【在 s****1 的大作中提到】
: 如果显示器数目超过6个以上，
: 到中国城，拿几张免费报纸，找到做厨柜的装修公司
: 打电话问他们自己有一个定制的家具，看看他们能不能做
: 其实牌子货都overpriced，还是上meritline买
【在 s****1 的大作中提到】
: 如果显示器数目超过6个以上，
: 到中国城，拿几张免费报纸，找到做厨柜的装修公司
: 打电话问他们自己有一个定制的家具，看看他们能不能做
: 其实牌子货都overpriced，还是上meritline买
g*y
14 楼
curious, how to do merge sort in place for array?
【在 k*k 的大作中提到】
: in-place stable merge sort?
: i may be wrong....
【在 k*k 的大作中提到】
: in-place stable merge sort?
: i may be wrong....
a*n
15 楼
我以为是I94上面的那个章，应该没事。只要你们是合法出入境。I94会上交然后
记录你们离境日期的。
【在 y********n 的大作中提到】
: 人已经回国了，不知如何补盖？会不会对下次签证造成影响呢，因为现在护照页上只有
: 中国出入境记录，没有相应的美国的出入境记录。
记录你们离境日期的。
【在 y********n 的大作中提到】
: 人已经回国了，不知如何补盖？会不会对下次签证造成影响呢，因为现在护照页上只有
: 中国出入境记录，没有相应的美国的出入境记录。
b*t
16 楼
如果是真的，那这两家就是水货商新宠了
【在 d*****g 的大作中提到】
: http://www.tipb.com/2011/10/12/sprint-verizon-offer-iphone-4s-u
【在 d*****g 的大作中提到】
: http://www.tipb.com/2011/10/12/sprint-verizon-offer-iphone-4s-u
s*1
17 楼
一台显示器为嘛需要arm?
【在 a*****w 的大作中提到】
: 就一个dell 2408wfp,自用的
【在 a*****w 的大作中提到】
: 就一个dell 2408wfp,自用的
S*Y
18 楼
how about space?
【在 g*******y 的大作中提到】
: 分冶可以做到O(nlogn)
: 对left right半截分别解决子问题，然后得到:
: {neg_left},{pos_left} | {neg_right},{pos_right}
: 再把{pos_left}跟{neg_right}调换位置就行了(就是个简单的数组rotate)
【在 g*******y 的大作中提到】
: 分冶可以做到O(nlogn)
: 对left right半截分别解决子问题，然后得到:
: {neg_left},{pos_left} | {neg_right},{pos_right}
: 再把{pos_left}跟{neg_right}调换位置就行了(就是个简单的数组rotate)
y*n
19 楼
是护照页上的入境章，当时大意了没仔细检查，头次遇上这种怪事，本来想父母作为
DEPENDENT报税的，现在也没有凭证了，无法向IRS证明父母在美时间。
【在 a*****n 的大作中提到】
: 我以为是I94上面的那个章，应该没事。只要你们是合法出入境。I94会上交然后
: 记录你们离境日期的。
DEPENDENT报税的，现在也没有凭证了，无法向IRS证明父母在美时间。
【在 a*****n 的大作中提到】
: 我以为是I94上面的那个章，应该没事。只要你们是合法出入境。I94会上交然后
: 记录你们离境日期的。
g*y
20 楼
all in place
【在 S**Y 的大作中提到】
: how about space?
【在 S**Y 的大作中提到】
: how about space?
S*Y
21 楼
no no..i am not saying the merging step
i mean generally, recursion requires a stack and the space is not constant(j
ust my guess).
【在 g*******y 的大作中提到】
: all in place
i mean generally, recursion requires a stack and the space is not constant(j
ust my guess).
【在 g*******y 的大作中提到】
: all in place
g*y
22 楼
not necessarily use recursive call
you can do something like
for(i=1;i!=N;i<<1){
for(j=0;j!=N;j+=i){
}
}
but it's a little more complicated to write the code than recursive call
Anyway, it's a very good question~
(j
【在 S**Y 的大作中提到】
: no no..i am not saying the merging step
: i mean generally, recursion requires a stack and the space is not constant(j
: ust my guess).
you can do something like
for(i=1;i!=N;i<<1){
for(j=0;j!=N;j+=i){
}
}
but it's a little more complicated to write the code than recursive call
Anyway, it's a very good question~
(j
【在 S**Y 的大作中提到】
: no no..i am not saying the merging step
: i mean generally, recursion requires a stack and the space is not constant(j
: ust my guess).
k*k
23 楼
cool solution.
>>
curious, how to do merge sort in place for array?
besides, even if you implement in place merge sort for linkedlist, I think
it will not be stable any more...
>>
that is why i think i maybe wrong.... i just faintly remembered i saw that
somewhere...
【在 g*******y 的大作中提到】
: 分冶可以做到O(nlogn)
: 对left right半截分别解决子问题，然后得到:
: {neg_left},{pos_left} | {neg_right},{pos_right}
: 再把{pos_left}跟{neg_right}调换位置就行了(就是个简单的数组rotate)
>>
curious, how to do merge sort in place for array?
besides, even if you implement in place merge sort for linkedlist, I think
it will not be stable any more...
>>
that is why i think i maybe wrong.... i just faintly remembered i saw that
somewhere...
【在 g*******y 的大作中提到】
: 分冶可以做到O(nlogn)
: 对left right半截分别解决子问题，然后得到:
: {neg_left},{pos_left} | {neg_right},{pos_right}
: 再把{pos_left}跟{neg_right}调换位置就行了(就是个简单的数组rotate)
g*y
24 楼
hehe, at least I don't know how to merge sort in place for array.
besidse, my comment about "in place merge sort for linkedlist will not be
stable" was not true. It could be stable. That's why I edited my post and
removed that part of comment.
【在 k*k 的大作中提到】
: cool solution.
: >>
: curious, how to do merge sort in place for array?
: besides, even if you implement in place merge sort for linkedlist, I think
: it will not be stable any more...
: >>
: that is why i think i maybe wrong.... i just faintly remembered i saw that
: somewhere...
besidse, my comment about "in place merge sort for linkedlist will not be
stable" was not true. It could be stable. That's why I edited my post and
removed that part of comment.
【在 k*k 的大作中提到】
: cool solution.
: >>
: curious, how to do merge sort in place for array?
: besides, even if you implement in place merge sort for linkedlist, I think
: it will not be stable any more...
: >>
: that is why i think i maybe wrong.... i just faintly remembered i saw that
: somewhere...
S*Y
25 楼
what do u mean? two for loops?
u still need to simulate recursion using a stack, which is still not o(1) sp
ace.
【在 g*******y 的大作中提到】
: not necessarily use recursive call
: you can do something like
: for(i=1;i!=N;i<<1){
: for(j=0;j!=N;j+=i){
: }
: }
: but it's a little more complicated to write the code than recursive call
: Anyway, it's a very good question~
:
: (j
u still need to simulate recursion using a stack, which is still not o(1) sp
ace.
【在 g*******y 的大作中提到】
: not necessarily use recursive call
: you can do something like
: for(i=1;i!=N;i<<1){
: for(j=0;j!=N;j+=i){
: }
: }
: but it's a little more complicated to write the code than recursive call
: Anyway, it's a very good question~
:
: (j
g*y
26 楼
yes. two for loops, outside loop takes logN iterations.
I don't need to simulate recursion call for this problem, please look at my two loops again.
or look at below
{a,b},{c,d},{e,f},{g,h}
{a,b,c,d},{e,f,g,h}
{a,b,c,d,e,f,g,h}
sp
【在 S**Y 的大作中提到】
: what do u mean? two for loops?
: u still need to simulate recursion using a stack, which is still not o(1) sp
: ace.
I don't need to simulate recursion call for this problem, please look at my two loops again.
or look at below
{a,b},{c,d},{e,f},{g,h}
{a,b,c,d},{e,f,g,h}
{a,b,c,d,e,f,g,h}
sp
【在 S**Y 的大作中提到】
: what do u mean? two for loops?
: u still need to simulate recursion using a stack, which is still not o(1) sp
: ace.
s*x
27 楼
其实就是对{ 1,1,0,0,1,0,1}排序，要求原地、稳定的排序算法。
【在 l*******r 的大作中提到】
: {1，5， -5， -8，2， -1，15 }
: 要把负的扫到左边，正的扫到后边。
: 不能改变顺序
: 得到{-5 -8 -1 1 5 2 15}
: 这个题有time 低于 n^2 space=O（1）的解法吗
【在 l*******r 的大作中提到】
: {1，5， -5， -8，2， -1，15 }
: 要把负的扫到左边，正的扫到后边。
: 不能改变顺序
: 得到{-5 -8 -1 1 5 2 15}
: 这个题有time 低于 n^2 space=O（1）的解法吗
t*y
28 楼
为啥我觉得跟sort没关系呢
1 -1 -8
是变成-1 -8 1吧。。。不是-8 -1 1吧。。。
扫一遍，记录负的位置就够了吧。
【在 l*******r 的大作中提到】
: {1，5， -5， -8，2， -1，15 }
: 要把负的扫到左边，正的扫到后边。
: 不能改变顺序
: 得到{-5 -8 -1 1 5 2 15}
: 这个题有time 低于 n^2 space=O（1）的解法吗
1 -1 -8
是变成-1 -8 1吧。。。不是-8 -1 1吧。。。
扫一遍，记录负的位置就够了吧。
【在 l*******r 的大作中提到】
: {1，5， -5， -8，2， -1，15 }
: 要把负的扫到左边，正的扫到后边。
: 不能改变顺序
: 得到{-5 -8 -1 1 5 2 15}
: 这个题有time 低于 n^2 space=O（1）的解法吗
g*y
29 楼
int k = 1; while(k
for(int j=0;j
if(pos2>=N) continue;
//找当前这段，左半边第一个正数
while(arr[pos1]<0 && pos1
while(pos2
//开始对换左边的所有正数和右边的所有负数
int p1 = pos1, p2 = pos2-1;
while(p1
【在 g*******y 的大作中提到】
: yes. two for loops, outside loop takes logN iterations.
: I don't need to simulate recursion call for this problem, please look at my two loops again.
: or look at below
: {a,b},{c,d},{e,f},{g,h}
: {a,b,c,d},{e,f,g,h}
: {a,b,c,d,e,f,g,h}
:
: sp
for(int j=0;j
if(pos2>=N) continue;
//找当前这段，左半边第一个正数
while(arr[pos1]<0 && pos1
while(pos2
//开始对换左边的所有正数和右边的所有负数
int p1 = pos1, p2 = pos2-1;
while(p1
【在 g*******y 的大作中提到】
: yes. two for loops, outside loop takes logN iterations.
: I don't need to simulate recursion call for this problem, please look at my two loops again.
: or look at below
: {a,b},{c,d},{e,f},{g,h}
: {a,b,c,d},{e,f,g,h}
: {a,b,c,d,e,f,g,h}
:
: sp
k*k
30 楼
@geniusxsy:
这个算法是 nlogn 吗？
1) while(k log N
2) for(int i=2; i<=k;i=i<<1) ==> log K
3) for(int j=0;j N/i == N/log K
4) the content of the inner most loop seems to me has N complexity worst
case.
so seems to me 2)*3)*4) already N^2
很可能是我哪里没搞明白。。。
先谢谢了。
int k = 1;
while(k
for(int j=0;j
if(pos2>=N) continue;
//找当前这段，左半边第一个正数
while(arr[pos1]<0 && pos1
这个算法是 nlogn 吗？
1) while(k
2) for(int i=2; i<=k;i=i<<1) ==> log K
3) for(int j=0;j
4) the content of the inner most loop seems to me has N complexity worst
case.
so seems to me 2)*3)*4) already N^2
很可能是我哪里没搞明白。。。
先谢谢了。
int k = 1;
while(k
for(int j=0;j
if(pos2>=N) continue;
//找当前这段，左半边第一个正数
while(arr[pos1]<0 && pos1
g*y
31 楼
怪mitbbs了，显示不了tab缩进，每行都变成左对齐了。。。呵呵
while(k)就是单独的一句话(单独的一个loop),跟下面两个for loops没关系。
while(k)的作用，只是要计算一个等于或者约大于N的2的整次方数。
其实我完全也可以把while(k)改写成：
k = 1 << (Log2(N-1)+1);
至于你说的2,3,4要O(N^2)是不对的，整个j loop做完，也就是O(N).
所以最后复杂度就是 log(k) * O(N) = O(NlogN)
这个本质上就是一个divide-conquer的非递归实现，复杂度当然不会有变化。
【在 k*k 的大作中提到】
: @geniusxsy:
: 这个算法是 nlogn 吗？
: 1) while(k log N
: 2) for(int i=2; i<=k;i=i<<1) ==> log K
: 3) for(int j=0;j N/i == N/log K
: 4) the content of the inner most loop seems to me has N complexity worst
: case.
: so seems to me 2)*3)*4) already N^2
: 很可能是我哪里没搞明白。。。
: 先谢谢了。
while(k)就是单独的一句话(单独的一个loop),跟下面两个for loops没关系。
while(k)的作用，只是要计算一个等于或者约大于N的2的整次方数。
其实我完全也可以把while(k)改写成：
k = 1 << (Log2(N-1)+1);
至于你说的2,3,4要O(N^2)是不对的，整个j loop做完，也就是O(N).
所以最后复杂度就是 log(k) * O(N) = O(NlogN)
这个本质上就是一个divide-conquer的非递归实现，复杂度当然不会有变化。
【在 k*k 的大作中提到】
: @geniusxsy:
: 这个算法是 nlogn 吗？
: 1) while(k
: 2) for(int i=2; i<=k;i=i<<1) ==> log K
: 3) for(int j=0;j
: 4) the content of the inner most loop seems to me has N complexity worst
: case.
: so seems to me 2)*3)*4) already N^2
: 很可能是我哪里没搞明白。。。
: 先谢谢了。
k*k
32 楼
miss this line...
int pos1 = j, pos2 = j+i/2;
thanks
int pos1 = j, pos2 = j+i/2;
thanks
f*6
33 楼
How about this:
1. find the number of pos numbers, pos
2. find the number of neg numbers, neg
3. scan array from right to left, for each neg number, shift it to the
beginning of the array.
repeat this for neg times.
4. scan array from left to right, for each pos number, shift it to the end
of the array.
repeat this for pos times.
example:
{1，5， -5， -8，2， -1，15 }
pos = 4; neg = 3
step 3:
{-1，1，5， -5， -8，2， 15 }
{-8，-1，1，5， -5， 2， 15 }
{-5， -8，-1，1，5， 2， 15 }
step 4:
{-5， -8，-1，5， 2， 15,
1. find the number of pos numbers, pos
2. find the number of neg numbers, neg
3. scan array from right to left, for each neg number, shift it to the
beginning of the array.
repeat this for neg times.
4. scan array from left to right, for each pos number, shift it to the end
of the array.
repeat this for pos times.
example:
{1，5， -5， -8，2， -1，15 }
pos = 4; neg = 3
step 3:
{-1，1，5， -5， -8，2， 15 }
{-8，-1，1，5， -5， 2， 15 }
{-5， -8，-1，1，5， 2， 15 }
step 4:
{-5， -8，-1，5， 2， 15,
p*9
34 楼
k和N相关，里面还有一层N，这已经是N^2了
【在 g*******y 的大作中提到】
: int k = 1; while(k
: for(int j=0;j
: if(pos2>=N) continue;
: //找当前这段，左半边第一个正数
: while(arr[pos1]<0 && pos1
: while(pos2
【在 g*******y 的大作中提到】
: int k = 1; while(k
: for(int j=0;j
: if(pos2>=N) continue;
: //找当前这段，左半边第一个正数
: while(arr[pos1]<0 && pos1
: while(pos2
p*9
35 楼
楼主好像是想找比N^2快的算法。
【在 f*****6 的大作中提到】
: How about this:
: 1. find the number of pos numbers, pos
: 2. find the number of neg numbers, neg
: 3. scan array from right to left, for each neg number, shift it to the
: beginning of the array.
: repeat this for neg times.
: 4. scan array from left to right, for each pos number, shift it to the end
: of the array.
: repeat this for pos times.
: example:
【在 f*****6 的大作中提到】
: How about this:
: 1. find the number of pos numbers, pos
: 2. find the number of neg numbers, neg
: 3. scan array from right to left, for each neg number, shift it to the
: beginning of the array.
: repeat this for neg times.
: 4. scan array from left to right, for each pos number, shift it to the end
: of the array.
: repeat this for pos times.
: example:
g*y
36 楼
无语了。。。
【在 p*********9 的大作中提到】
: k和N相关，里面还有一层N，这已经是N^2了
【在 p*********9 的大作中提到】
: k和N相关，里面还有一层N，这已经是N^2了
p*9
37 楼
sorry,看错了。
但是最外面两层loop已经是Nlog(N)了，里面还有跟j相关的loop，所以这个复杂度比
Nlog(N)高了。
还有一点没有看明白，最后交换的时候，您老是怎么保证order的？特别是正数的长度
和负数的长度不一致的时候
【在 g*******y 的大作中提到】
: 无语了。。。
但是最外面两层loop已经是Nlog(N)了，里面还有跟j相关的loop，所以这个复杂度比
Nlog(N)高了。
还有一点没有看明白，最后交换的时候，您老是怎么保证order的？特别是正数的长度
和负数的长度不一致的时候
【在 g*******y 的大作中提到】
: 无语了。。。
m*f
38 楼
我也有类似的疑问, 前面是 nlogn 毫无疑问, 但是这里三个while, 先交换了
左边的正数和右边的负数, 然后再分别调换次序保证顺序正确, 这里能保证是
O(1)?
左边的正数和右边的负数, 然后再分别调换次序保证顺序正确, 这里能保证是
O(1)?
m*f
39 楼
后面还有一次交换阿, 第一交换正数负数的时候如果某方过长, 会造成正数和正数, 或
者负数同负数的交换, 后面第二次就能换回正确位置.
【在 p*********9 的大作中提到】
: sorry,看错了。
: 但是最外面两层loop已经是Nlog(N)了，里面还有跟j相关的loop，所以这个复杂度比
: Nlog(N)高了。
: 还有一点没有看明白，最后交换的时候，您老是怎么保证order的？特别是正数的长度
: 和负数的长度不一致的时候
者负数同负数的交换, 后面第二次就能换回正确位置.
【在 p*********9 的大作中提到】
: sorry,看错了。
: 但是最外面两层loop已经是Nlog(N)了，里面还有跟j相关的loop，所以这个复杂度比
: Nlog(N)高了。
: 还有一点没有看明白，最后交换的时候，您老是怎么保证order的？特别是正数的长度
: 和负数的长度不一致的时候
g*y
40 楼
有疑问的同学，建议看看我3楼，12楼的帖子。再看看code。
如果还有疑问的，不妨贴去编译运行一下。当然，如果你找到bug的话可以告诉我一下
，呵呵，至少我自己test了几次都通过了的
如果还有疑问的，不妨贴去编译运行一下。当然，如果你找到bug的话可以告诉我一下
，呵呵，至少我自己test了几次都通过了的
p*9
41 楼
哦，明白了。多谢，多谢
【在 m*****f 的大作中提到】
: 后面还有一次交换阿, 第一交换正数负数的时候如果某方过长, 会造成正数和正数, 或
: 者负数同负数的交换, 后面第二次就能换回正确位置.
【在 m*****f 的大作中提到】
: 后面还有一次交换阿, 第一交换正数负数的时候如果某方过长, 会造成正数和正数, 或
: 者负数同负数的交换, 后面第二次就能换回正确位置.
k*k
42 楼
is your array rotation technique generally applicable?
given an array such as
[+ + + + - - -]
i will do following:
1) compute the len of neg. segement
2) reverse the whole array
3) reverse the neg seg given its len
4) reverse the remaining pos seg
compare to your approach mine need an extra step (step 1)
//step 2-3 can be trimmed down to N if using GCD tricks.
I try to apply your sol. on following array
int arr[9] = {-7, -8, 9, -6, -11, -3, -5, 2, 3};
and set
j=0; N = 9;
pos1 = 2; pos2 = 7;
i th
given an array such as
[+ + + + - - -]
i will do following:
1) compute the len of neg. segement
2) reverse the whole array
3) reverse the neg seg given its len
4) reverse the remaining pos seg
compare to your approach mine need an extra step (step 1)
//step 2-3 can be trimmed down to N if using GCD tricks.
I try to apply your sol. on following array
int arr[9] = {-7, -8, 9, -6, -11, -3, -5, 2, 3};
and set
j=0; N = 9;
pos1 = 2; pos2 = 7;
i th
g*y
43 楼
hi, this part of my code is a specialized version of shifting array (the
quantity j+i/2 is not for general purpose)
You need to modify it for general purpose.
【在 k*k 的大作中提到】
: is your array rotation technique generally applicable?
: given an array such as
: [+ + + + - - -]
: i will do following:
: 1) compute the len of neg. segement
: 2) reverse the whole array
: 3) reverse the neg seg given its len
: 4) reverse the remaining pos seg
: compare to your approach mine need an extra step (step 1)
: //step 2-3 can be trimmed down to N if using GCD tricks.
quantity j+i/2 is not for general purpose)
You need to modify it for general purpose.
【在 k*k 的大作中提到】
: is your array rotation technique generally applicable?
: given an array such as
: [+ + + + - - -]
: i will do following:
: 1) compute the len of neg. segement
: 2) reverse the whole array
: 3) reverse the neg seg given its len
: 4) reverse the remaining pos seg
: compare to your approach mine need an extra step (step 1)
: //step 2-3 can be trimmed down to N if using GCD tricks.
w*p
44 楼
类似qsort要用O(nlogn) space, merge sort要用O(n) space, 不合要求
有关array shift, rotate 的操作running time 是O(n), 也不合要求
用linked list O(n)running time 和 O(1) space
1, you have a linked list for {1，5， -5， -8，2， -1，15 }
2. remember the original linked list head, scan all note one by one, if
the
number is negative, remove it from the original liked list, and put it to
new linked list, you will get
1, 5, 2, 15
-5, -8, -1,
3. link the tail of second linked list to head of original linked list
-5, -8, -1, 1, 5, 2, 1
有关array shift, rotate 的操作running time 是O(n), 也不合要求
用linked list O(n)running time 和 O(1) space
1, you have a linked list for {1，5， -5， -8，2， -1，15 }
2. remember the original linked list head, scan all note one by one, if
the
number is negative, remove it from the original liked list, and put it to
new linked list, you will get
1, 5, 2, 15
-5, -8, -1,
3. link the tail of second linked list to head of original linked list
-5, -8, -1, 1, 5, 2, 1
f*r
45 楼
这题有超级复杂无比的O(N)+O(1)的算法. 要用到in-place cache的方法.
AOP的习题中有一道题和这个很像.
【在 l*******r 的大作中提到】
: {1，5， -5， -8，2， -1，15 }
: 要把负的扫到左边，正的扫到后边。
: 不能改变顺序
: 得到{-5 -8 -1 1 5 2 15}
: 这个题有time 低于 n^2 space=O（1）的解法吗
AOP的习题中有一道题和这个很像.
【在 l*******r 的大作中提到】
: {1，5， -5， -8，2， -1，15 }
: 要把负的扫到左边，正的扫到后边。
: 不能改变顺序
: 得到{-5 -8 -1 1 5 2 15}
: 这个题有time 低于 n^2 space=O（1）的解法吗
w*p
46 楼
土土的问：啥是AOP的习题？有link 吗？
【在 f*********r 的大作中提到】
: 这题有超级复杂无比的O(N)+O(1)的算法. 要用到in-place cache的方法.
: AOP的习题中有一道题和这个很像.
【在 f*********r 的大作中提到】
: 这题有超级复杂无比的O(N)+O(1)的算法. 要用到in-place cache的方法.
: AOP的习题中有一道题和这个很像.
k*e
47 楼
不是吧，要请出这本书。如果真的谁搞定了这套书，我相信他是不屑来bbs和偶们交流
的。估计直接联系billgates了。
【在 f*********r 的大作中提到】
: 这题有超级复杂无比的O(N)+O(1)的算法. 要用到in-place cache的方法.
: AOP的习题中有一道题和这个很像.
的。估计直接联系billgates了。
【在 f*********r 的大作中提到】
: 这题有超级复杂无比的O(N)+O(1)的算法. 要用到in-place cache的方法.
: AOP的习题中有一道题和这个很像.
S*Y
48 楼
faint..似乎确实是O(nlogn)
虽然里面有while循环，但是第二个for循环(using j)并没有遍历全部元素，而是跳跃的
，后面的while循环填补了跳跃的元素，刚好是O(n)...
【在 g*******y 的大作中提到】
: int k = 1; while(k
: for(int j=0;j
: if(pos2>=N) continue;
: //找当前这段，左半边第一个正数
: while(arr[pos1]<0 && pos1
: while(pos2
虽然里面有while循环，但是第二个for循环(using j)并没有遍历全部元素，而是跳跃的
，后面的while循环填补了跳跃的元素，刚好是O(n)...
【在 g*******y 的大作中提到】
: int k = 1; while(k
: for(int j=0;j
: if(pos2>=N) continue;
: //找当前这段，左半边第一个正数
: while(arr[pos1]<0 && pos1
: while(pos2
S*Y
49 楼
是。用这个思路也可以实现非recursive的merge sort,不过还是需要额外的空间的。
【在 g*******y 的大作中提到】
: 怪mitbbs了，显示不了tab缩进，每行都变成左对齐了。。。呵呵
: while(k)就是单独的一句话(单独的一个loop),跟下面两个for loops没关系。
: while(k)的作用，只是要计算一个等于或者约大于N的2的整次方数。
: 其实我完全也可以把while(k)改写成：
: k = 1 << (Log2(N-1)+1);
: 至于你说的2,3,4要O(N^2)是不对的，整个j loop做完，也就是O(N).
: 所以最后复杂度就是 log(k) * O(N) = O(NlogN)
: 这个本质上就是一个divide-conquer的非递归实现，复杂度当然不会有变化。
【在 g*******y 的大作中提到】
: 怪mitbbs了，显示不了tab缩进，每行都变成左对齐了。。。呵呵
: while(k)就是单独的一句话(单独的一个loop),跟下面两个for loops没关系。
: while(k)的作用，只是要计算一个等于或者约大于N的2的整次方数。
: 其实我完全也可以把while(k)改写成：
: k = 1 << (Log2(N-1)+1);
: 至于你说的2,3,4要O(N^2)是不对的，整个j loop做完，也就是O(N).
: 所以最后复杂度就是 log(k) * O(N) = O(NlogN)
: 这个本质上就是一个divide-conquer的非递归实现，复杂度当然不会有变化。
相关阅读
找Technician位置，Philadelphia/NJ附近how to draw a scale bar大清早来问个问题有下周去旧金山AACR Translational Cancer的吗？Genetics of Tibetans (转载)我该怎么办要不要离婚 (转载)请问如何筛选悬浮细胞的稳定株有没有这样的分子?我的转行经验---凑或者看吧，也算是原创的。Chase Sapphire Card信用卡开户送1万点($100)博后选择Western help我见过的千老转行最远的大分子量蛋白(300KD)的Western Blot transfer时间要多少?在线等.谢谢!paper help please关于Nature 投稿的编号这里有人该行作 打假的吗Help, website for checking NIH funding?Job Opening in cardiovascular pharmacology or physiology (U (转载)