l***i
发帖数: 1309 | 1 Given an int array of positive and negative numbers, rearrange it in O(1)
extra space such that all positive numbers are on the left and all negative
numbers are on the right, and the relative order of positive numbers, and
the relative order of the negative numbers are the same as in the input.
Can it be done in O(n)? |
r****o
发帖数: 1950 | 2 问个简单问题，什么叫stable rearrange?
negative
【在 l***i 的大作中提到】
: Given an int array of positive and negative numbers, rearrange it in O(1)
: extra space such that all positive numbers are on the left and all negative
: numbers are on the right, and the relative order of positive numbers, and
: the relative order of the negative numbers are the same as in the input.
: Can it be done in O(n)?
|
l***i
发帖数: 1309 | 3 The relative orders are preserved.
Example:
input [-5 -7 3 4 -2 9 -1 7]
output [ 3 4 9 7 -5 -7 -2 -1] |
r**u
发帖数: 1567 | 4 我觉得不能O(n)。这个跟bubble sort差不多。
negative
【在 l***i 的大作中提到】
: Given an int array of positive and negative numbers, rearrange it in O(1)
: extra space such that all positive numbers are on the left and all negative
: numbers are on the right, and the relative order of positive numbers, and
: the relative order of the negative numbers are the same as in the input.
: Can it be done in O(n)?
|
r****o
发帖数: 1950 | 5 我觉得时间复杂度可以O(n)阿，
先全部扫描一篇，统计有多少正数和负数，假定正数个数和负数个数分别为n1和n2。
然后再扫描一遍，根据n1和n2我们可以知道这些数在新数组中的位置。
不过空间复杂度好像也要O(n)。
【在 r**u 的大作中提到】
: 我觉得不能O(n)。这个跟bubble sort差不多。
:
: negative
|
l***i
发帖数: 1309 | 6 Divide and conquer can give you nlogn. But I don't know if O(n) is possible. |
r****o
发帖数: 1950 | 7 能不能说说你的Divide and conquer算法阿，呵呵。
possible.
【在 l***i 的大作中提到】
: Divide and conquer can give you nlogn. But I don't know if O(n) is possible.
|
l***i
发帖数: 1309 | 8 split into two halves, solve each half recursively, then do some swaps to
get the positive subarray from right to left and the negative subarray from
right to left. |
r**u
发帖数: 1567 | 9 我觉得不对，in-place的话，每个element移动到对应的位置都是要O(n)步，无论用啥
法子。所以overall复杂度还是O(n^2)。
from
【在 l***i 的大作中提到】
: split into two halves, solve each half recursively, then do some swaps to
: get the positive subarray from right to left and the negative subarray from
: right to left.
|
l***i
发帖数: 1309 | |
r**u
发帖数: 1567 | 11 so what? 你能把你O(nlogn)算法具体写出来，给个例子么？dude，不要想当然。
【在 l***i 的大作中提到】
: dude, this is an array
|
o*******7
发帖数: 13 | 12 O(n)还是有希望的。虽然每个element移动最坏情况下确实要O(n)步，但是如果设计巧
妙的话，有可能并不是每一个
element都需要O(n)，这样amortize下来，也许最后能平均成O(1). 最后也许O(n)就能
解决...
但是具体怎么做还没想到。
【在 r**u 的大作中提到】
: 我觉得不对，in-place的话，每个element移动到对应的位置都是要O(n)步，无论用啥
: 法子。所以overall复杂度还是O(n^2)。
:
: from
|
c*****y
发帖数: 90 | 13 好像不行，你试一个例子。
to
from
【在 l***i 的大作中提到】
: split into two halves, solve each half recursively, then do some swaps to
: get the positive subarray from right to left and the negative subarray from
: right to left.
|
