C*******n
发帖数: 56 | 1 一个数组，就只有正数和负数，要把正数排在数组前面，负数排在后面，同时保持这些
数跟原来的顺序一致，比如，－1，3， －2， 4， 7＝＝》3, 4, 7, -1, -2.
要求O(n)时间，O(1)空间。 |
r**l
发帖数: 31 | 2 doubt this can be done in O(n) time and O(1) space,
either
O(n^2) time and O(1) space
or
O(n) time and O(n) space
anybody? |
t*****j
发帖数: 1105 | 3 这个其实就是移车位问题的变体，所以可以O（n）时间 O(1) space的。
【在 C*******n 的大作中提到】
: 一个数组，就只有正数和负数，要把正数排在数组前面，负数排在后面，同时保持这些
: 数跟原来的顺序一致，比如，－1，3， －2， 4， 7＝＝》3, 4, 7, -1, -2.
: 要求O(n)时间，O(1)空间。
|
r**l
发帖数: 31 | 4
any hints pls?
【在 t*****j 的大作中提到】
: 这个其实就是移车位问题的变体，所以可以O（n）时间 O(1) space的。
|
t*****j
发帖数: 1105 | 5 你查 parking lot问题，有讨论的。
【在 r**l 的大作中提到】
:
: any hints pls?
|
f****g
发帖数: 313 | 6 Hey, todayzj
Could you share the link for the discussion? I tried several key words, and
but
I still cannot find it..
I think without the constraints of keeping the same order of the elements,
it
is easy to be done in O(n) time and O(1) space ( refer to the implementation
of
qsort)
【在 t*****j 的大作中提到】
: 你查 parking lot问题，有讨论的。
|
t*****j
发帖数: 1105 | 7 right....我要想想是不是真的和parking lot完全对应。刚刚我也是随口一说。那个pa
rking lot问题我找了下，在此：
http://www.mitbbs.com/article/JobHunting/31553037_3.html
and
implementation
【在 f****g 的大作中提到】
: Hey, todayzj
: Could you share the link for the discussion? I tried several key words, and
: but
: I still cannot find it..
: I think without the constraints of keeping the same order of the elements,
: it
: is easy to be done in O(n) time and O(1) space ( refer to the implementation
: of
: qsort)
|
f****g
发帖数: 313 | 8 I got it.
First round, place all the positive numbers in fronts of negative numbers. (
refer the implementation of qsort pivot placement) O(n) time
So the positive numbers are in order and negative numbers are in reserved
order.
Second round, swap the negative numbers to put them in order. O(n) time
Over all it is O(n) |
t*****j
发帖数: 1105 | 9 好像是对的～～～厉害啊～～
(
【在 f****g 的大作中提到】
: I got it.
: First round, place all the positive numbers in fronts of negative numbers. (
: refer the implementation of qsort pivot placement) O(n) time
: So the positive numbers are in order and negative numbers are in reserved
: order.
: Second round, swap the negative numbers to put them in order. O(n) time
: Over all it is O(n)
|
f****g
发帖数: 313 | 10 Unfortunately, I found the flaw about my solution :(
I could make sure the positive part in the right order, and the negative
part
is not exactly in the reserved order :(
【在 t*****j 的大作中提到】
: 好像是对的～～～厉害啊～～
:
: (
|
|
|
t*****j
发帖数: 1105 | 11 I realized it too when I am cooking...
【在 f****g 的大作中提到】
: Unfortunately, I found the flaw about my solution :(
: I could make sure the positive part in the right order, and the negative
: part
: is not exactly in the reserved order :(
|
f****g
发帖数: 313 | 12 wow, you could think about problem when cooking~~~
Wondering what do you cook? haha
【在 t*****j 的大作中提到】
: I realized it too when I am cooking...
|
c******r
发帖数: 300 | 13 If the numbers are stored in a list, i think you can do it by using O(n)
insertion/deletion operators and O(1) space. You just need to keep a pointer
to store the place for the next positive number and then you delete postive
number when necessary and insert it at the pointer.
【在 C*******n 的大作中提到】
: 一个数组，就只有正数和负数，要把正数排在数组前面，负数排在后面，同时保持这些
: 数跟原来的顺序一致，比如，－1，3， －2， 4， 7＝＝》3, 4, 7, -1, -2.
: 要求O(n)时间，O(1)空间。
|
f***g
发帖数: 214 | 14 parking lot的题没完全理解。
我所知道的最好的算法是
Div - Con.
1. base case: 数组只有两个数，就不用说了吧
2. merge:
两个subarray, 必定是前面正后面负的形式，
例如： [1 2 3 -4 -5] [6 7 -8 -9]
只要做rotation就行了。 |
j********x
发帖数: 2330 | 15 估计跟inplace shuffling有关系
one pass scan可以得到正数和负数的分界，然后直接shuffle到指定位置好了 |
j********x
发帖数: 2330 | |
c*****e
发帖数: 74 | 17 前面怎么也没想通，刚刚画了个图就明白了。
First consider a special problem: write a function
/*
In Time complexity (m+n) & Space complexity O(1), move the subarray starting
at nIdx with length of (m+n) (the first m numbers and the later n numbers)
such that (1) n numbers are ahead of m numbers and (2) the order inside the
m number and n numbers are not changed
*/
void MoveAdjacentMN(int* p, /* address of the array */
int nIdx, /* initial index for m+n numbers in the array */
int m,
int n)
Sketch idea: if m == n, swap pair by pair;
if m > n, swap the last n numbers of m numbers with the n
numbers, and then solve problem MoveAdjacentMN(p, nIdx,m-n,n)
if m < n, swap the first m numbers of n numbers with the m
numbers, and then solve problem MoveAdjacentMN(p, nIdx + m ,m,n - m)
Complexity of MoveAdjacentMN: space is constant (just not use recursion);
time complexity is linear since the size of the problem is decreased by m(or
n) and the time complexity needed is also linear of m(or n). [Please help
correct me if this is not true]. |
b********h
发帖数: 119 | 18 11 Node* partition(Node* head)
12 {
13 Node* positive = NULL;
14 Node* tail = NULL;
15
16 Node* first = head;
17 Node* second = NULL;
18 while(first) {
19 if(first->val > 0)
20 {
21 Node* tmp = first;
22 first = first->next;
23
24 // delete
25 if(second)
26 second->next = first;
27
28 tmp->next = NULL;
29
30 // insert
31 if(!positive)
32 positive = tmp;
33 else
34 tail->next = tmp;
35
36 tail = tmp;
37 }
38 else
39 {
40 second = first;
41 first = first->next;
42 }
43 }
44
45 // merge
46 if(positive)
47 {
48 tail->next = head;
49 head = positive;
50 }
51
52 return head;
53 } |
g*********s
发帖数: 1782 | 19 1. lz states it's array, not linked list.
2. A descriptive writing would be much more helpful than a code segment w/o
any comments.
【在 b********h 的大作中提到】
: 11 Node* partition(Node* head)
: 12 {
: 13 Node* positive = NULL;
: 14 Node* tail = NULL;
: 15
: 16 Node* first = head;
: 17 Node* second = NULL;
: 18 while(first) {
: 19 if(first->val > 0)
: 20 {
|
g*********s
发帖数: 1782 | 20 I agree with u.
【在 r**l 的大作中提到】
: doubt this can be done in O(n) time and O(1) space,
: either
: O(n^2) time and O(1) space
: or
: O(n) time and O(n) space
: anybody?
|
|
|
b********h
发帖数: 119 | 21 我觉得有问题。这个似乎不是线性的。比如这个例子：
-1 2 -3 4
先做-1和2的swap，没问题，变成
2 -1 -3 4
这时候你要做-1 -3和4的swap，-1继续参与运算。所以某些数可能参与了好多次运算。
这个问题是数组的话好像没有简单的解。链表的话就是我上面贴的代码。
starting
)
the
【在 c*****e 的大作中提到】
: 前面怎么也没想通，刚刚画了个图就明白了。
: First consider a special problem: write a function
: /*
: In Time complexity (m+n) & Space complexity O(1), move the subarray starting
: at nIdx with length of (m+n) (the first m numbers and the later n numbers)
: such that (1) n numbers are ahead of m numbers and (2) the order inside the
: m number and n numbers are not changed
: */
: void MoveAdjacentMN(int* p, /* address of the array */
: int nIdx, /* initial index for m+n numbers in the array */
|
b*****e
发帖数: 474 | 22 Hmmm, very interesting little problem indeed. Here is an evil approach:
A little thought will convince you that you can scan the array in O(n) time
and know exactly the target index (t_i) for each array element a_i. The
question is, how to store that information (a_i, t_i), i.e. two numbers, in
the array a[] (that hold one number in each element)?
Well, we can use the value M = max(|a_i|)+1 (- the max value is again the by
-product of a previous linear scan), and, rewrite
the array value a[i] to be (t_i+1)*M + a_i.
Thus, t_i = a[i]/M-1, a_i = a[i] % M. So relax, we can get the two values
back easily.
Now we can use the following method to replace old with new:
int start=0;
while ( start != end of array ) {
k=start;
p = a[k];
while ( a[k] is not in the right place, i.e. a[k]>=M) {
let t_i = the target of p
save temp = a[t_i];
insert p into right place t_i;
k = the target of temp ;
p = temp;
}
start ++;
}
This is a nested loop but is O(n) time. The inner loop basically cycles
through the chain of replaced values until the chain goes back to the
beginning, so each value is replaced only once and never will be in the
inner loop again.
Of course, if the M value trick causes number overflow (i.e. (n+1)*M is too
big), this method won't work. So this is really just an evil hack, nothing
more. |
i********s
发帖数: 133 | 23 Very interesting solution.
time
in
by
【在 b*****e 的大作中提到】
: Hmmm, very interesting little problem indeed. Here is an evil approach:
: A little thought will convince you that you can scan the array in O(n) time
: and know exactly the target index (t_i) for each array element a_i. The
: question is, how to store that information (a_i, t_i), i.e. two numbers, in
: the array a[] (that hold one number in each element)?
: Well, we can use the value M = max(|a_i|)+1 (- the max value is again the by
: -product of a previous linear scan), and, rewrite
: the array value a[i] to be (t_i+1)*M + a_i.
: Thus, t_i = a[i]/M-1, a_i = a[i] % M. So relax, we can get the two values
: back easily.
|
