请问这件guess的moto jacket留吗？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Fashion - 美丽时尚

请问这件guess的moto jacket留吗？

请问这件guess的moto jacket留吗？# Fashion - 美丽时尚

l*n2010-09-05 07:09

1 楼

Given an array of +ve and -ve integers, re-arrange it so that u have +ves on
one end and -ves on other, but we have to retain the order of appearance.
for eg,
1,7,-5,9,-12,15
ans=
-5,-12,1,7,9,15
is it possible to do it in O(n) without using extra space ? If not possible,
can it be done with O(n) and O(1) space?
网上查答案，看了好些网站，一直没找到合适的解法。请大牛指教。

s*a2010-09-05 07:09

2 楼

jms觉得这个好看吗？
全价买的值不值？
事物没这么皱~ 是平展的~
谢谢
http://shop.guess.com/Catalog/View/Women/Jackets%20_and_%20Outerwear/Scarlett%20Jacket/W0F220MU868
//他们也太不敬业了广告pic也不挂几天平了再照。。。

c*m2010-09-05 07:09

3 楼

without extra space 和 O(1) 有啥区别？
swap两个数算不算without extra space？

p*m2010-09-05 07:09

4 楼

留好看我有件类似红色的。

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

: jms觉得这个好看吗？
: 全价买的值不值？
: 事物没这么皱~ 是平展的~
: 谢谢
: http://shop.guess.com/Catalog/View/Women/Jackets%20_and_%20Outerwear/Scarlett%20Jacket/W0F220MU868
: //他们也太不敬业了广告pic也不挂几天平了再照。。。

S*t2010-09-05 07:09

5 楼

not sure if it's impossible for O(N) time + in-place, but it's definitely
non-trivial even for a special case of "in-shuffle" (perfect shuffle), as in
the paper:
http://arxiv.org/pdf/0805.1598.pdf

on
possible,

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

: Given an array of +ve and -ve integers, re-arrange it so that u have +ves on
: one end and -ves on other, but we have to retain the order of appearance.
: for eg,
: 1,7,-5,9,-12,15
: ans=
: -5,-12,1,7,9,15
: is it possible to do it in O(n) without using extra space ? If not possible,
: can it be done with O(n) and O(1) space?
: 网上查答案，看了好些网站，一直没找到合适的解法。请大牛指教。

s*m2010-09-05 07:09

6 楼

我觉得这个长度，有点土。。。。

S*t2010-09-05 07:09

7 楼

swap: a = a ^ b, b = a ^ b, a = a ^ b

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

: without extra space 和 O(1) 有啥区别？
: swap两个数算不算without extra space？

m*i2010-09-05 07:09

8 楼

个子高的话，留吧。挺好看的

w*x2010-09-05 07:09

9 楼

Make a boundary pointer to track where the boundary between neg and pos.
Scan the array with regular iterator, once the value is neg, swap with the
boundary pointers value. then boundary pointer++.

on
possible,

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

G*a2010-09-05 07:09

10 楼

会不会很短啊。。。。

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

d*k2010-09-05 07:09

11 楼

这题有O(n)，O(1）的方法，不过那些算法都是发过paper的，很复杂。
我说个O(nlogn)，O(1)的吧：分治法，分别处理左右两半，同时返回正负分界点(第一
个正数的下标)，合并只需将左半边的正数（右侧）和右半边的负数(左侧）交换即可。
Online coding一把，欢迎review.
# should call sort(array, 0, len(array) - 1)
def sort(array, left, right):
if left > right:
return 0
if left == right:
return left if array[left] > 0 or left + 1
mid = (left + right) / 2
x = sort(array, left, m - 1)
y = sort(array, m, right)
mid_rev(array, x, m, y - 1)
return x + y - m
def mid_rev(array, x, m, y):
if not x < m <= y:
return
r = y - m + 1
rev(array, x, y)
rev(array, x, x + r － 1)
rev(array, x + r, y)
def rev(array, x, y):
while x < y:
array[x], array[y] = array[y], array[x]
x += 1
y -= 1

s*a2010-09-05 07:09

12 楼

呵呵是挺短的。。。
后面比前面还短

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

: 会不会很短啊。。。。

e*82010-09-05 07:09

13 楼

这个方法挺巧妙～～
后面交换（左半边的正数，右半边的负数）的方法，好象就是in place rotate数组的
办法吧？

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

: 这题有O(n)，O(1）的方法，不过那些算法都是发过paper的，很复杂。
: 我说个O(nlogn)，O(1)的吧：分治法，分别处理左右两半，同时返回正负分界点(第一
: 个正数的下标)，合并只需将左半边的正数（右侧）和右半边的负数(左侧）交换即可。
: Online coding一把，欢迎review.
: # should call sort(array, 0, len(array) - 1)
: def sort(array, left, right):
: if left > right:
: return 0
: if left == right:
: return left if array[left] > 0 or left + 1