c*********t
发帖数: 2921 | 1 谁有那个帖子的link?好像那个帖子消失了。
好像是说给了一个整数array,有正数，有负数，要求把负数放在前面，正数放在后面，
同时保持顺序不变。
给个例子：
5 3 -2 9 -8 4 7 -10 6
结果应该是
-2 -8 -10 5 3 9 4 7 6
好像要求是O(n), in-place
大家讨论的结论是:
如果in-place,不可能O(n);
如果可以用额外的空间，可以很容易做到O(n).
有个人提到in-place,可以O(n logn),他没有说如何实现，这个如何做？我实在想不出
来。
我只能想出O(n^2) 的in-place的方法。 | r*******y
发帖数: 1081 | 2 coask
【在 c*********t 的大作中提到】
: 谁有那个帖子的link?好像那个帖子消失了。
: 好像是说给了一个整数array,有正数，有负数，要求把负数放在前面，正数放在后面，
: 同时保持顺序不变。
: 给个例子：
: 5 3 -2 9 -8 4 7 -10 6
: 结果应该是
: -2 -8 -10 5 3 9 4 7 6
: 好像要求是O(n), in-place
: 大家讨论的结论是:
: 如果in-place,不可能O(n);
| d*******d
发帖数: 2050 | 3 divide and conquer
直接写的,没试过,不知道对不对.
int switch(int * a, int start, int end){
if( start > end)
return -1;
if( start == end){
if( a[start] < 0)
return 1;
else
return 0;
int mid = (start+ end)/2;
int left = switch(a, start, mid);
int right = switch(a, mid+1, end);
int total_neg = 0;
if( left>0)
total_neg+= left;
if( right>0)
total_neg+= right;
if( right > 0 && mid-start+1 - left >0 ){
reverse(a, start+left+1, mid+right);
reverse(a, start+left+1, start+left+right);
reverse(a, start+left+right+1, mid+right);
}
return total_neg;
} | f****4
发帖数: 1359 | | c*********t
发帖数: 2921 | 5 谢谢！你的方法很好。
我想到了分治法，可是当时不知道如何把已经排好序的两段如何merge.
你用了类似于rotate string的方法来实现in-place rotate，把第一段里的正数部分和
第二段里的负数部分rotate.
【在 d*******d 的大作中提到】
: divide and conquer
: 直接写的,没试过,不知道对不对.
: int switch(int * a, int start, int end){
: if( start > end)
: return -1;
: if( start == end){
: if( a[start] < 0)
: return 1;
: else
: return 0;
| m**q
发帖数: 189 | 6 赞！这个in-place的rotate在这类题目里面还是挺有用的
略微扩展一下，如果原题目要把数组划分成负数，0，整数，
并保持原来的顺序，可以先把0从数组中删掉，然后用
这个分治的算法，最后再把0加进来就行。
刚想起来一个以前看过的类似的问题，也是用分治的方法解决，
复杂度O(nlgn)
把数组A1, A2, ..., An, B1, B2, ..., Bn 变为
A1, B1, A2, B2, ..., An, Bn，
一个例子: abcdefg1234567 -> a1b2c3d4e5f6g7
用O(n)的in-place rotate方法,把数组分成两半
abcd1234 efg567
然后递归处理每个子问题就可以了，区别是这里
要先rotate再分治，原题是先分治再rotate
【在 c*********t 的大作中提到】
: 谢谢！你的方法很好。
: 我想到了分治法，可是当时不知道如何把已经排好序的两段如何merge.
: 你用了类似于rotate string的方法来实现in-place rotate，把第一段里的正数部分和
: 第二段里的负数部分rotate.
| c*********t
发帖数: 2921 | 7 maxq,
你说的方法来interleave 数组A, B，我写了代码好像不work.
可能是我写错了，还是你的方法有问题？
http://www.mitbbs.com/article_t/JobHunting/31946827.html
的第二题就是问的这个问题。
你能给详细解答一下吗？
【在 m**q 的大作中提到】
: 赞！这个in-place的rotate在这类题目里面还是挺有用的
: 略微扩展一下，如果原题目要把数组划分成负数，0，整数，
: 并保持原来的顺序，可以先把0从数组中删掉，然后用
: 这个分治的算法，最后再把0加进来就行。
: 刚想起来一个以前看过的类似的问题，也是用分治的方法解决，
: 复杂度O(nlgn)
: 把数组A1, A2, ..., An, B1, B2, ..., Bn 变为
: A1, B1, A2, B2, ..., An, Bn，
: 一个例子: abcdefg1234567 -> a1b2c3d4e5f6g7
: 用O(n)的in-place rotate方法,把数组分成两半
| d*******d
发帖数: 2050 | 8 这个问题要考虑分治后每个subproblem的奇偶问题.
你自己再研究研究,不行我再贴code
【在 c*********t 的大作中提到】
: maxq,
: 你说的方法来interleave 数组A, B，我写了代码好像不work.
: 可能是我写错了，还是你的方法有问题？
: http://www.mitbbs.com/article_t/JobHunting/31946827.html
: 的第二题就是问的这个问题。
: 你能给详细解答一下吗？
|
| f*******t
发帖数: 7549 | 9 请贴code吧。。。有个问题我不知道怎么解决：当n=5的时候，rotate不是简单的交换。
a1a2a3a4a5b1b2b3b4b5 -> a1a2a3b1b2b3a4a5b4b5
需要把b的前三项与a的后两项交换
程序实在不知道怎么写
【在 d*******d 的大作中提到】
: 这个问题要考虑分治后每个subproblem的奇偶问题.
: 你自己再研究研究,不行我再贴code
| d*******d
发帖数: 2050 | 10 好吧,如下code是我当练习直接写的,没有验证,
有问题的话,我再去把正确code翻出来
void swap(char * a, int start, int n){
for( int i = 0; i< n; i++){
char temp = a[start + i];
a[start+i] = a[start+i-n];
a[start+i-n] = temp;
}
}
void shiftpos(char * a, int start, int end){
if( end - start <= 1)
return;
int first_half_end = (end + start)/2;
int first_half_n = first_half_end - start + 1;
swap(a,first_half_end+1, first_half_n/2);
shiftpos(a, start, first_half_end);
if( first_half_n & 1){
shiftpos(a, first_half_end, end);
}else{
shiftpos(a, first_half_end+1, end);
}
} | | | c******o
发帖数: 534 | 11 这个swap是O（n）？
【在 d*******d 的大作中提到】
: 好吧,如下code是我当练习直接写的,没有验证,
: 有问题的话,我再去把正确code翻出来
: void swap(char * a, int start, int n){
: for( int i = 0; i< n; i++){
: char temp = a[start + i];
: a[start+i] = a[start+i-n];
: a[start+i-n] = temp;
: }
: }
: void shiftpos(char * a, int start, int end){
| c******o
发帖数: 534 | 12 这个容易懂，谢谢了
【在 d*******d 的大作中提到】
: divide and conquer
: 直接写的,没试过,不知道对不对.
: int switch(int * a, int start, int end){
: if( start > end)
: return -1;
: if( start == end){
: if( a[start] < 0)
: return 1;
: else
: return 0;
| f*******t
发帖数: 7549 | 13 应该是对的，感谢分享！
【在 d*******d 的大作中提到】
: 好吧,如下code是我当练习直接写的,没有验证,
: 有问题的话,我再去把正确code翻出来
: void swap(char * a, int start, int n){
: for( int i = 0; i< n; i++){
: char temp = a[start + i];
: a[start+i] = a[start+i-n];
: a[start+i-n] = temp;
: }
: }
: void shiftpos(char * a, int start, int end){
| c*********t
发帖数: 2921 | 14 Dino,
你太牛了。对的。
你能不能说说你的rationale?
你是怎么想到了如果前半部分个数是奇数，第二个subproblem的时候就是从mid开始？
如果前半部分个数是偶数，第二个subproblem的时候就是从mid+1开始？
另外你是如何 figure out 按照前半段的一半的长度来交换的？
比如 a b c 1 2 3 ===> a b 1 c 2 3
谢谢！
【在 d*******d 的大作中提到】
: 好吧,如下code是我当练习直接写的,没有验证,
: 有问题的话,我再去把正确code翻出来
: void swap(char * a, int start, int n){
: for( int i = 0; i< n; i++){
: char temp = a[start + i];
: a[start+i] = a[start+i-n];
: a[start+i-n] = temp;
: }
: }
: void shiftpos(char * a, int start, int end){
| r*******g
发帖数: 1335 | 15 这种题现场做很难做到bugfree啊，知道思路了就是这个奇偶问题都要把人弄死。。。
【在 c*********t 的大作中提到】
: Dino,
: 你太牛了。对的。
: 你能不能说说你的rationale?
: 你是怎么想到了如果前半部分个数是奇数，第二个subproblem的时候就是从mid开始？
: 如果前半部分个数是偶数，第二个subproblem的时候就是从mid+1开始？
: 另外你是如何 figure out 按照前半段的一半的长度来交换的？
: 比如 a b c 1 2 3 ===> a b 1 c 2 3
: 谢谢！
| f*******t
发帖数: 7549 | 16 我还专门研究过，程序运行是以下步骤：
start: a b c 1 2 3
swap: a b 1 c 2 3
shift first half: [a b 1] c 2 3 -> a 1 b c 2 3
shift second half: a 1 [b c 2 3] -> a 1 b 2 c 3
done
dino这程序太牛了，完美解决奇偶性的问题
【在 c*********t 的大作中提到】
: Dino,
: 你太牛了。对的。
: 你能不能说说你的rationale?
: 你是怎么想到了如果前半部分个数是奇数，第二个subproblem的时候就是从mid开始？
: 如果前半部分个数是偶数，第二个subproblem的时候就是从mid+1开始？
: 另外你是如何 figure out 按照前半段的一半的长度来交换的？
: 比如 a b c 1 2 3 ===> a b 1 c 2 3
: 谢谢！
| h******3
发帖数: 351 | 17 I am not sure I understand the solution correctly.
Let's consider this input:
{3,5,4,-2,-3,-1}
expected output should be
{-2,-3,-1,3,5,4}
consider the stack information of the final step:
start = 0; end = 5; left = 0; right = 3; mid = 2
reverse(start+left+1, mid+right)-> reverse{5,4,-2,-3,-1}, we get {3,-1,-3,-2
,4,5}
reverse(start+left+1, start+left+right)-> reverse{-1,-3,-2} we get
{3,-2,-3,-1,4,5}
reverse(start+left+right+1, mid+right)->reverse{4,5} we get
{3,-2,-3,-1,5,4}
which is not correct.
I think the first index of the first two reverse should start+left instead
of start+left+1.
【在 d*******d 的大作中提到】
: divide and conquer
: 直接写的,没试过,不知道对不对.
: int switch(int * a, int start, int end){
: if( start > end)
: return -1;
: if( start == end){
: if( a[start] < 0)
: return 1;
: else
: return 0;
| k*j
发帖数: 153 | 18 这个是O(nlgn)，不是O(n)吧？
【在 d*******d 的大作中提到】
: divide and conquer
: 直接写的,没试过,不知道对不对.
: int switch(int * a, int start, int end){
: if( start > end)
: return -1;
: if( start == end){
: if( a[start] < 0)
: return 1;
: else
: return 0;
| s**x
发帖数: 405 | 19 this problem is at least as difficult as the in-place perfect shuffle
problem (turn 1A2B3C4D5E to 12345ABCDE in O(1) space and O(n) time); the
latter can be viewed as a special case | c*********t
发帖数: 2921 | 20 shyx,
turn 1A2B3C4D5E to 12345ABCDE
和
turn 12345ABCDE to 1A2B3C4D5E
是不是一样的难？是不是这两个题的思路差不多？
谢谢！
【在 s**x 的大作中提到】
: this problem is at least as difficult as the in-place perfect shuffle
: problem (turn 1A2B3C4D5E to 12345ABCDE in O(1) space and O(n) time); the
: latter can be viewed as a special case
| k*j
发帖数: 153 | 21 想请教一下各位，这个dino提出的in-place rotate的方法为什么是O(n)的？
f(n) = 2f(n/2)+O(n),应该是O(nlgn)吧？
【在 m**q 的大作中提到】
: 赞！这个in-place的rotate在这类题目里面还是挺有用的
: 略微扩展一下，如果原题目要把数组划分成负数，0，整数，
: 并保持原来的顺序，可以先把0从数组中删掉，然后用
: 这个分治的算法，最后再把0加进来就行。
: 刚想起来一个以前看过的类似的问题，也是用分治的方法解决，
: 复杂度O(nlgn)
: 把数组A1, A2, ..., An, B1, B2, ..., Bn 变为
: A1, B1, A2, B2, ..., An, Bn，
: 一个例子: abcdefg1234567 -> a1b2c3d4e5f6g7
: 用O(n)的in-place rotate方法,把数组分成两半
|
|
