l**********n
发帖数: 303 | 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?
网上查答案，看了好些网站，一直没找到合适的解法。请大牛指教。 | c**m
发帖数: 535 | 2 without extra space 和 O(1) 有啥区别？
swap两个数算不算without extra space？ | S********t
发帖数: 3431 | 3 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********t
发帖数: 3431 | 4 swap: a = a ^ b, b = a ^ b, a = a ^ b
【在 c**m 的大作中提到】
: without extra space 和 O(1) 有啥区别？
: swap两个数算不算without extra space？
| w**x
发帖数: 362 | 5 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 的大作中提到】
: 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?
: 网上查答案，看了好些网站，一直没找到合适的解法。请大牛指教。
| d*k
发帖数: 207 | 6 这题有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
| e*******8
发帖数: 94 | 7 这个方法挺巧妙～～
后面交换（左半边的正数，右半边的负数）的方法，好象就是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
|
|
