i*********7
发帖数: 348 | 1 就是将数组里的负数排在数组的前面，正数排在数组的后面。但不改变原先负数和正数
的排列顺序。
例：input:-5，2，-3,4，-8，-9,1,3，-10
output: -5,-3,-8,-9,-10,2,4,1,3
原本要求是in place, time o(n), space o(1)
我看了版上关于这题目的大部分评论，好像大部分都在热议time o(nlogn) space o(1)
是可行的。
现在我只想求一个time o(nlogn) space o(1)解法的具体思路或者算法。。谢谢。。 | t*********7
发帖数: 255 | 2 两个INDEX一前一后,前正后负就互换;前负后正就前递增,后递减;都负前递增;都正后递
减. | p*****2
发帖数: 21240 | 3
顺序就变了。
【在 t*********7 的大作中提到】
: 两个INDEX一前一后,前正后负就互换;前负后正就前递增,后递减;都负前递增;都正后递
: 减.
| t*********7
发帖数: 255 | 4
没注意还要保持顺序...
【在 p*****2 的大作中提到】
:
: 顺序就变了。
| s******n
发帖数: 3946 | 5 大概思路这样；
void arrange(int *a, int length, int& countof)
{
int count_of_neg1, count_of_neg2；
arrange(a, length/2, count_of_neg1);
arrange(a+length/2, length-length/2, count_of_neg2);
rotate(...); // 左面部分的正数和右半部的负数rotate。
}
关键在rotate的实现，每次rotate有(length/2)次交换的算法，总计的rotate时间是O(
length/2 + length/4 + .... +1) = O(length) | w****x
发帖数: 2483 | | c*********t
发帖数: 2921 | 7 所以说，你的方法的复杂度还是 O(nlogn),对吧？！
O(
【在 s******n 的大作中提到】
: 大概思路这样；
: void arrange(int *a, int length, int& countof)
: {
: int count_of_neg1, count_of_neg2；
: arrange(a, length/2, count_of_neg1);
: arrange(a+length/2, length-length/2, count_of_neg2);
: rotate(...); // 左面部分的正数和右半部的负数rotate。
: }
: 关键在rotate的实现，每次rotate有(length/2)次交换的算法，总计的rotate时间是O(
: length/2 + length/4 + .... +1) = O(length)
| s******n
发帖数: 3946 | 8 想了想，好像比O(nlogn)更高，呵呵
【在 c*********t 的大作中提到】
: 所以说，你的方法的复杂度还是 O(nlogn),对吧？！
:
: O(
| l*********8
发帖数: 4642 | 9 应该就是O(nlogn)
【在 s******n 的大作中提到】
: 想了想，好像比O(nlogn)更高，呵呵
| g**u
发帖数: 504 | 10 This divide and conquer can achieve O(nlogn). It seems O(nlogn) is optimal
with the constraints of no extra space and in place. Is there any way to
achieve O(n)?
【在 w****x 的大作中提到】
: my blog:
: http://haixiaoyang.wordpress.com/2012/03/21/stable-2-way-partit
| | | a***g
发帖数: 234 | 11 这样的话average是nlogn, worst case是n^2吧
O(
【在 s******n 的大作中提到】
: 大概思路这样；
: void arrange(int *a, int length, int& countof)
: {
: int count_of_neg1, count_of_neg2；
: arrange(a, length/2, count_of_neg1);
: arrange(a+length/2, length-length/2, count_of_neg2);
: rotate(...); // 左面部分的正数和右半部的负数rotate。
: }
: 关键在rotate的实现，每次rotate有(length/2)次交换的算法，总计的rotate时间是O(
: length/2 + length/4 + .... +1) = O(length)
| m******6
发帖数: 82 | 12 1.找到最小的>0的数，然后设为pivot
2.然后做一次in-place partition
不知道对不对
1)
【在 i*********7 的大作中提到】
: 就是将数组里的负数排在数组的前面，正数排在数组的后面。但不改变原先负数和正数
: 的排列顺序。
: 例：input:-5，2，-3,4，-8，-9,1,3，-10
: output: -5,-3,-8,-9,-10,2,4,1,3
: 原本要求是in place, time o(n), space o(1)
: 我看了版上关于这题目的大部分评论，好像大部分都在热议time o(nlogn) space o(1)
: 是可行的。
: 现在我只想求一个time o(nlogn) space o(1)解法的具体思路或者算法。。谢谢。。
| i*********7
发帖数: 348 | 13 用quicksort的思路的话，就会有不stable的结果。。。
【在 m******6 的大作中提到】
: 1.找到最小的>0的数，然后设为pivot
: 2.然后做一次in-place partition
: 不知道对不对
:
: 1)
| c***p
发帖数: 221 | 14 可以用类似merge sort的方法。
在merge的时候，把前一段中的正数和后一段的负数作swap，然后再分别作swap，保持
原来的order。
时间复杂度是nlogn.
1)
【在 i*********7 的大作中提到】
: 就是将数组里的负数排在数组的前面，正数排在数组的后面。但不改变原先负数和正数
: 的排列顺序。
: 例：input:-5，2，-3,4，-8，-9,1,3，-10
: output: -5,-3,-8,-9,-10,2,4,1,3
: 原本要求是in place, time o(n), space o(1)
: 我看了版上关于这题目的大部分评论，好像大部分都在热议time o(nlogn) space o(1)
: 是可行的。
: 现在我只想求一个time o(nlogn) space o(1)解法的具体思路或者算法。。谢谢。。
| a***g
发帖数: 234 | 15 这个好
【在 c***p 的大作中提到】
: 可以用类似merge sort的方法。
: 在merge的时候，把前一段中的正数和后一段的负数作swap，然后再分别作swap，保持
: 原来的order。
: 时间复杂度是nlogn.
:
: 1)
| a*******8
发帖数: 110 | 16 merg sort要O(n) space吧
【在 c***p 的大作中提到】
: 可以用类似merge sort的方法。
: 在merge的时候，把前一段中的正数和后一段的负数作swap，然后再分别作swap，保持
: 原来的order。
: 时间复杂度是nlogn.
:
: 1)
| c***p
发帖数: 221 | 17 merge sort 要O(n) space.
但是，就这个题目只是作partition, swap就可以了，所以可以in-place完成。不需要
额外空间。
【在 a*******8 的大作中提到】
: merg sort要O(n) space吧
| b*********3
发帖数: 748 | 18 为啥？先扫一遍找到最小的正整数，O(n)。再从头开始，比这个整数小的都在左边，
order retained。总的只要O(n)
【在 i*********7 的大作中提到】
: 用quicksort的思路的话，就会有不stable的结果。。。
| l*********8
发帖数: 4642 | 19 这里的stable是指： “不改变原先负数和正数的排列顺序”
我估计你理解的stable是指“最差情况下，仍然有相同的时间复杂度”。
【在 b*********3 的大作中提到】
: 为啥？先扫一遍找到最小的正整数，O(n)。再从头开始，比这个整数小的都在左边，
: order retained。总的只要O(n)
| t**r
发帖数: 3428 | | | | d****n
发帖数: 1637 | 21 my solution
runningtime
space O(1)
any suggestions or improvement?
///file mitbbs.c
#include
int arr[]={-5,2,-3,4,-8,-9,1,3,-10};
int sz=9;
void print_arr();
int main(){
print_arr();
int i,j,k,t;
for(i=0,k=0;i
if(arr[i]<0 ){
t=arr[i];
for(j=i-1;j>=k ;j-- ){
arr[j+1]=arr[j];
}
arr[k]=t;
k++;
}
}
print_arr();
}
///output
-5 2 -3 4 -8 -9 1 3 -10
-5 -3 -8 -9 -10 2 4 1 3 | l*********8
发帖数: 4642 | 22 这个应该是O(n^2)。 两层循环， 每层都是O(N)
(n)
【在 d****n 的大作中提到】
: my solution
: runningtime : space O(1)
: any suggestions or improvement?
: ///file mitbbs.c
: #include
: int arr[]={-5,2,-3,4,-8,-9,1,3,-10};
: int sz=9;
: void print_arr();
: int main(){
| d****n
发帖数: 1637 | 23 It never goes to n^2. try it
【在 l*********8 的大作中提到】
: 这个应该是O(n^2)。 两层循环， 每层都是O(N)
:
: (n)
| l*********8
发帖数: 4642 | 24 假设数组左边 n/2个都是正数，右边n/2个都是负数。
你的方法大致做到了 (n/2)^2 次move, it's O(n^2)
【在 d****n 的大作中提到】
: It never goes to n^2. try it
| d****n
发帖数: 1637 | 25 那就block by block的move。这样能优化。
还真没想到你得worst case。
我想到的是fully shuffled case
等我再优化下。
【在 l*********8 的大作中提到】
: 假设数组左边 n/2个都是正数，右边n/2个都是负数。
: 你的方法大致做到了 (n/2)^2 次move, it's O(n^2)
|
|
