l*******r
发帖数: 511 | 1 {1，5， -5， -8，2， -1，15 }
要把负的扫到左边，正的扫到后边。
不能改变顺序
得到{-5 -8 -1 1 5 2 15}
这个题有time 低于 n^2 space=O（1）的解法吗 | k*k
发帖数: 49 | 2 in-place stable merge sort?
i may be wrong.... | g*******y
发帖数: 1930 | 3 分冶可以做到O(nlogn)
对left right半截分别解决子问题，然后得到:
{neg_left},{pos_left} | {neg_right},{pos_right}
再把{pos_left}跟{neg_right}调换位置就行了(就是个简单的数组rotate) | g*******y
发帖数: 1930 | 4 curious, how to do merge sort in place for array?
【在 k*k 的大作中提到】
: in-place stable merge sort?
: i may be wrong....
| S**Y
发帖数: 136 | 5 how about space?
【在 g*******y 的大作中提到】
: 分冶可以做到O(nlogn)
: 对left right半截分别解决子问题，然后得到:
: {neg_left},{pos_left} | {neg_right},{pos_right}
: 再把{pos_left}跟{neg_right}调换位置就行了(就是个简单的数组rotate)
| g*******y
发帖数: 1930 | 6 all in place
【在 S**Y 的大作中提到】
: how about space?
| S**Y
发帖数: 136 | 7 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
| g*******y
发帖数: 1930 | 8 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).
|
| k*k
发帖数: 49 | 9 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)
| g*******y
发帖数: 1930 | 10 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...
| | | S**Y
发帖数: 136 | 11 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
| g*******y
发帖数: 1930 | 12 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.
| s*x
发帖数: 3328 | 13 其实就是对{ 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）的解法吗
| t*****y
发帖数: 31 | 14 为啥我觉得跟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）的解法吗
| g*******y
发帖数: 1930 | 15 int k = 1; while(k
for(int i=2; i<=k;i=i<<1){ //k是刚刚大于等于N的某个2的整次方数
for(int j=0;j
int pos1 = j, pos2 = j+i/2;
if(pos2>=N) continue;
//找当前这段，左半边第一个正数
while(arr[pos1]<0 && pos1
//找当前这段，右半边第一个正数
while(pos2
if(pos1 == j+i/2 || pos2==j+i/2) continue;
//开始对换左边的所有正数和右边的所有负数
int p1 = pos1, p2 = pos2-1;
while(p1
p1 = pos1; p2 =
【在 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
发帖数: 49 | 16 @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 i=2; i<=k;i=i<<1){ //k是刚刚大于等于N的某个2的整次方数
for(int j=0;j
int pos1 = j, pos2 = j+i/2;
if(pos2>=N) continue;
//找当前这段，左半边第一个正数
while(arr[pos1]<0 && pos1
//找当前这段，右半边第 | g*******y
发帖数: 1930 | 17 怪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
: 很可能是我哪里没搞明白。。。
: 先谢谢了。
| k*k
发帖数: 49 | 18 miss this line...
int pos1 = j, pos2 = j+i/2;
thanks | f*****6
发帖数: 63 | 19 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, | p*********9
发帖数: 30 | 20 k和N相关，里面还有一层N，这已经是N^2了
【在 g*******y 的大作中提到】
: int k = 1; while(k: for(int i=2; i<=k;i=i<<1){ //k是刚刚大于等于N的某个2的整次方数
: for(int j=0;j: int pos1 = j, pos2 = j+i/2;
: if(pos2>=N) continue;
: //找当前这段，左半边第一个正数
: while(arr[pos1]<0 && pos1: //找当前这段，右半边第一个正数
: while(pos2: if(pos1 == j+i/2 || pos2==j+i/2) continue;
| | | p*********9
发帖数: 30 | 21 楼主好像是想找比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:
| g*******y
发帖数: 1930 | 22 无语了。。。
【在 p*********9 的大作中提到】
: k和N相关，里面还有一层N，这已经是N^2了
| p*********9
发帖数: 30 | 23 sorry,看错了。
但是最外面两层loop已经是Nlog(N)了，里面还有跟j相关的loop，所以这个复杂度比
Nlog(N)高了。
还有一点没有看明白，最后交换的时候，您老是怎么保证order的？特别是正数的长度
和负数的长度不一致的时候
【在 g*******y 的大作中提到】
: 无语了。。。
| m*****f
发帖数: 1243 | 24 我也有类似的疑问, 前面是 nlogn 毫无疑问, 但是这里三个while, 先交换了
左边的正数和右边的负数, 然后再分别调换次序保证顺序正确, 这里能保证是
O(1)? | m*****f
发帖数: 1243 | 25 后面还有一次交换阿, 第一交换正数负数的时候如果某方过长, 会造成正数和正数, 或
者负数同负数的交换, 后面第二次就能换回正确位置.
【在 p*********9 的大作中提到】
: sorry,看错了。
: 但是最外面两层loop已经是Nlog(N)了，里面还有跟j相关的loop，所以这个复杂度比
: Nlog(N)高了。
: 还有一点没有看明白，最后交换的时候，您老是怎么保证order的？特别是正数的长度
: 和负数的长度不一致的时候
| g*******y
发帖数: 1930 | 26 有疑问的同学，建议看看我3楼，12楼的帖子。再看看code。
如果还有疑问的，不妨贴去编译运行一下。当然，如果你找到bug的话可以告诉我一下
，呵呵，至少我自己test了几次都通过了的 | p*********9
发帖数: 30 | 27 哦，明白了。多谢，多谢
【在 m*****f 的大作中提到】
: 后面还有一次交换阿, 第一交换正数负数的时候如果某方过长, 会造成正数和正数, 或
: 者负数同负数的交换, 后面第二次就能换回正确位置.
| k*k
发帖数: 49 | 28 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 | g*******y
发帖数: 1930 | 29 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.
| w********p
发帖数: 948 | 30 类似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 | | | f*********r
发帖数: 68 | 31 这题有超级复杂无比的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）的解法吗
| w********p
发帖数: 948 | 32 土土的问：啥是AOP的习题？有link 吗？
【在 f*********r 的大作中提到】
: 这题有超级复杂无比的O(N)+O(1)的算法. 要用到in-place cache的方法.
: AOP的习题中有一道题和这个很像.
| k***e
发帖数: 556 | 33 不是吧，要请出这本书。如果真的谁搞定了这套书，我相信他是不屑来bbs和偶们交流
的。估计直接联系billgates了。
【在 f*********r 的大作中提到】
: 这题有超级复杂无比的O(N)+O(1)的算法. 要用到in-place cache的方法.
: AOP的习题中有一道题和这个很像.
| S**Y
发帖数: 136 | 34 faint..似乎确实是O(nlogn)
虽然里面有while循环，但是第二个for循环(using j)并没有遍历全部元素，而是跳跃的
，后面的while循环填补了跳跃的元素，刚好是O(n)...
【在 g*******y 的大作中提到】
: int k = 1; while(k: for(int i=2; i<=k;i=i<<1){ //k是刚刚大于等于N的某个2的整次方数
: for(int j=0;j: int pos1 = j, pos2 = j+i/2;
: if(pos2>=N) continue;
: //找当前这段，左半边第一个正数
: while(arr[pos1]<0 && pos1: //找当前这段，右半边第一个正数
: while(pos2: if(pos1 == j+i/2 || pos2==j+i/2) continue;
| S**Y
发帖数: 136 | 35 是。用这个思路也可以实现非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的非递归实现，复杂度当然不会有变化。
|
|
