笑傲江湖里宋丹丹的儿子很搞笑的# TVChinese - 中文电视
C*n
1 楼
一个数组，就只有正数和负数，要把正数排在数组前面，负数排在后面，同时保持这些
数跟原来的顺序一致，比如，－1，3， －2， 4， 7＝＝》3, 4, 7, -1, -2.
要求O(n)时间，O(1)空间。
数跟原来的顺序一致，比如，－1，3， －2， 4， 7＝＝》3, 4, 7, -1, -2.
要求O(n)时间，O(1)空间。
s*o
2 楼
笑傲江湖里宋丹丹的儿子很搞笑的，叫什么纸片，结果让个说单口相声的
挤到第二去了，他的创意都挺好的，道具也都是自己搞的，让他给笑死了。
挤到第二去了，他的创意都挺好的，道具也都是自己搞的，让他给笑死了。
r*l
3 楼
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?
either
O(n^2) time and O(1) space
or
O(n) time and O(n) space
anybody?
w*m
4 楼
我要飞得更高，变身汪峰
t*j
5 楼
这个其实就是移车位问题的变体，所以可以O（n）时间 O(1) space的。
【在 C*******n 的大作中提到】
: 一个数组，就只有正数和负数，要把正数排在数组前面，负数排在后面，同时保持这些
: 数跟原来的顺序一致，比如，－1，3， －2， 4， 7＝＝》3, 4, 7, -1, -2.
: 要求O(n)时间，O(1)空间。
【在 C*******n 的大作中提到】
: 一个数组，就只有正数和负数，要把正数排在数组前面，负数排在后面，同时保持这些
: 数跟原来的顺序一致，比如，－1，3， －2， 4， 7＝＝》3, 4, 7, -1, -2.
: 要求O(n)时间，O(1)空间。
f*g
6 楼
现场认的便宜儿子，这得说清楚。
【在 s**********o 的大作中提到】
: 笑傲江湖里宋丹丹的儿子很搞笑的，叫什么纸片，结果让个说单口相声的
: 挤到第二去了，他的创意都挺好的，道具也都是自己搞的，让他给笑死了。
【在 s**********o 的大作中提到】
: 笑傲江湖里宋丹丹的儿子很搞笑的，叫什么纸片，结果让个说单口相声的
: 挤到第二去了，他的创意都挺好的，道具也都是自己搞的，让他给笑死了。
r*l
7 楼
any hints pls?
【在 t*****j 的大作中提到】
: 这个其实就是移车位问题的变体，所以可以O（n）时间 O(1) space的。
w*m
8 楼
让我就抱住了，认准一个妈，一辈子吃穿都不愁的，他的节目应该上春晚
【在 f****g 的大作中提到】
: 现场认的便宜儿子，这得说清楚。
【在 f****g 的大作中提到】
: 现场认的便宜儿子，这得说清楚。
t*j
9 楼
你查 parking lot问题，有讨论的。
【在 r**l 的大作中提到】
:
: any hints pls?
【在 r**l 的大作中提到】
:
: any hints pls?
f*g
10 楼
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问题，有讨论的。
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
11 楼
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)
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
12 楼
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)
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
13 楼
好像是对的～～～厉害啊～～
(
【在 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 的大作中提到】
: 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
14 楼
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 的大作中提到】
: 好像是对的～～～厉害啊～～
:
: (
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
15 楼
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 的大作中提到】
: 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
16 楼
wow, you could think about problem when cooking~~~
Wondering what do you cook? haha
【在 t*****j 的大作中提到】
: I realized it too when I am cooking...
Wondering what do you cook? haha
【在 t*****j 的大作中提到】
: I realized it too when I am cooking...
c*r
17 楼
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)空间。
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
18 楼
parking lot的题没完全理解。
我所知道的最好的算法是
Div - Con.
1. base case: 数组只有两个数，就不用说了吧
2. merge:
两个subarray, 必定是前面正后面负的形式，
例如： [1 2 3 -4 -5] [6 7 -8 -9]
只要做rotation就行了。
我所知道的最好的算法是
Div - Con.
1. base case: 数组只有两个数，就不用说了吧
2. merge:
两个subarray, 必定是前面正后面负的形式，
例如： [1 2 3 -4 -5] [6 7 -8 -9]
只要做rotation就行了。
j*x
19 楼
估计跟inplace shuffling有关系
one pass scan可以得到正数和负数的分界，然后直接shuffle到指定位置好了
one pass scan可以得到正数和负数的分界，然后直接shuffle到指定位置好了
j*x
20 楼
inplace merging吧
c*e
21 楼
前面怎么也没想通，刚刚画了个图就明白了。
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].
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
22 楼
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 }
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
23 楼
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 {
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
24 楼
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?
【在 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
25 楼
我觉得有问题。这个似乎不是线性的。比如这个例子：
-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 */
-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
26 楼
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.
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
27 楼
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.
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.
相关阅读
《梦想星搭档》今晚首播 女神冰冰客串亮相 (转载)龚琳娜降Key版《明月几时有》真是豪放大气上档次听这些美声和民族有两种耳朵。Txbb, 粉红猪小妹突然没了，能加回去吗？还是更喜欢小唐《最美和声》四强赛再听好声音只有这二人最近有看了《半泽直树》的吗？那个结局到底是怎么回事？请教为什么ruko1无法安装网星（已关闭防火墙）《谁与争锋》首席大力士VS鼻子吹气者假如生活欺骗了你 不错爸爸去哪儿主题曲好听啊推拿咋看不明白？致命名单谁在看？推荐《到爱的距离》haha, 成民歌版了龚琳娜之前不是记得老公是德国人吗？怎么半婊子中国海洋大学半婊子保研黑幕 2003年大连理工大学电子系考研失利的青岛二中学生邢慧强被中国海洋大学电子系破格录取为中国海洋大学电子系的硕士，如果给半婊子中国海洋大学加上一个形容词的话，我希望是全天线宝宝能不能加一个“老梁观世界”吴克群唱了些狗屎啊！