给点正能量 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EB23 - 劳工卡

给点正能量

给点正能量# EB23 - 劳工卡

i*72014-05-02 07:05

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*h2014-05-02 07:05

2 楼

TSC今天批了个RD 3/24的, 扫号扫出来的.
IO们still alive!!
[发表自未名空间手机版 - m.mitbbs.com]

t*72014-05-02 07:05

3 楼

两个INDEX一前一后,前正后负就互换;前负后正就前递增,后递减;都负前递增;都正后递
减.

F*u2014-05-02 07:05

4 楼

能看出是EB还是FB不？

【在 T*******h 的大作中提到】

: TSC今天批了个RD 3/24的, 扫号扫出来的.
: IO们still alive!!
: [发表自未名空间手机版 - m.mitbbs.com]

p*22014-05-02 07:05

5 楼

顺序就变了。

【在 t*********7 的大作中提到】

: 两个INDEX一前一后,前正后负就互换;前负后正就前递增,后递减;都负前递增;都正后递
: 减.

T*h2014-05-02 07:05

6 楼

看不出来.
前200个485,还有一个4/30批的;
后150个还没动静,有几个写的是document/card prod,但是具体些的是mail document,
感觉不像是绿

[发表自未名空间手机版 - m.mitbbs.com]

【在 F*********u 的大作中提到】

: 能看出是EB还是FB不？

t*72014-05-02 07:05

7 楼

没注意还要保持顺序...

【在 p*****2 的大作中提到】

:
: 顺序就变了。

F*u2014-05-02 07:05

8 楼

我是说往前看看，如果是concurrent filing
可能能看到I-140或者I-130 I-129F什么的？

【在 T*******h 的大作中提到】

: 看不出来.
: 前200个485,还有一个4/30批的;
: 后150个还没动静,有几个写的是document/card prod,但是具体些的是mail document,
: 感觉不像是绿
:
: [发表自未名空间手机版 - m.mitbbs.com]

s*n2014-05-02 07:05

9 楼

大概思路这样；
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)

T*h2014-05-02 07:05

10 楼

前一个号是485,后两个是765和131,是EB吧

[发表自未名空间手机版 - m.mitbbs.com]

【在 F*********u 的大作中提到】

: 我是说往前看看，如果是concurrent filing
: 可能能看到I-140或者I-130 I-129F什么的？

w*x2014-05-02 07:05

11 楼

my blog:
http://haixiaoyang.wordpress.com/2012/03/21/stable-2-way-partit

F*u2014-05-02 07:05

12 楼

不知道了，这些FB也可以有

【在 T*******h 的大作中提到】

: 前一个号是485,后两个是765和131,是EB吧
:
: [发表自未名空间手机版 - m.mitbbs.com]

c*t2014-05-02 07:05

13 楼

所以说，你的方法的复杂度还是 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)

H*i2014-05-02 07:05

14 楼

把扫号结果贴出来大家看看有没有自己的在里面。

s*n2014-05-02 07:05

15 楼

想了想，好像比O(nlogn)更高，呵呵

【在 c*********t 的大作中提到】

: 所以说，你的方法的复杂度还是 O(nlogn),对吧？！
:
: O(

l*82014-05-02 07:05

16 楼

应该就是O(nlogn)

【在 s******n 的大作中提到】

: 想了想，好像比O(nlogn)更高，呵呵

g*u2014-05-02 07:05

17 楼

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*g2014-05-02 07:05

18 楼

这样的话average是nlogn, worst case是n^2吧

O(

【在 s******n 的大作中提到】

m*62014-05-02 07:05

19 楼

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*72014-05-02 07:05

20 楼

用quicksort的思路的话，就会有不stable的结果。。。

【在 m******6 的大作中提到】

: 1.找到最小的>0的数，然后设为pivot
: 2.然后做一次in-place partition
: 不知道对不对
:
: 1)

c*p2014-05-02 07:05

21 楼

可以用类似merge sort的方法。
在merge的时候，把前一段中的正数和后一段的负数作swap，然后再分别作swap，保持
原来的order。
时间复杂度是nlogn.

1)

【在 i*********7 的大作中提到】

a*g2014-05-02 07:05

22 楼

这个好

【在 c***p 的大作中提到】

: 可以用类似merge sort的方法。
: 在merge的时候，把前一段中的正数和后一段的负数作swap，然后再分别作swap，保持
: 原来的order。
: 时间复杂度是nlogn.
:
: 1)

a*82014-05-02 07:05

23 楼

merg sort要O(n) space吧

【在 c***p 的大作中提到】

c*p2014-05-02 07:05

24 楼

merge sort 要O(n) space.
但是，就这个题目只是作partition, swap就可以了，所以可以in-place完成。不需要
额外空间。

【在 a*******8 的大作中提到】

: merg sort要O(n) space吧

b*32014-05-02 07:05

25 楼

为啥？先扫一遍找到最小的正整数，O(n)。再从头开始，比这个整数小的都在左边，
order retained。总的只要O(n)

【在 i*********7 的大作中提到】

: 用quicksort的思路的话，就会有不stable的结果。。。

l*82014-05-02 07:05

26 楼

这里的stable是指： “不改变原先负数和正数的排列顺序”
我估计你理解的stable是指“最差情况下，仍然有相同的时间复杂度”。

【在 b*********3 的大作中提到】

: 为啥？先扫一遍找到最小的正整数，O(n)。再从头开始，比这个整数小的都在左边，
: order retained。总的只要O(n)

t*r2014-05-02 07:05

27 楼

ｍａｒｋ

d*n2014-05-02 07:05

28 楼

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;iif(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*82014-05-02 07:05

29 楼

这个应该是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*n2014-05-02 07:05

30 楼

It never goes to n^2. try it

【在 l*********8 的大作中提到】

: 这个应该是O(n^2)。两层循环，每层都是O(N)
:
: (n)

l*82014-05-02 07:05

31 楼

假设数组左边 n/2个都是正数，右边n/2个都是负数。
你的方法大致做到了 (n/2)^2 次move, it's O(n^2)

【在 d****n 的大作中提到】

: It never goes to n^2. try it

d*n2014-05-02 07:05

32 楼

那就block by block的move。这样能优化。
还真没想到你得worst case。
我想到的是fully shuffled case
等我再优化下。

【在 l*********8 的大作中提到】

: 假设数组左边 n/2个都是正数，右边n/2个都是负数。
: 你的方法大致做到了 (n/2)^2 次move, it's O(n^2)