g*******i
发帖数: 95 | 1 给一个整数的ARRAY,有正有负有零，要求inplace变成先负数再零再正数(负数和正数内
部顺序不能
变)。 |
i**********e
发帖数: 1145 | 2 3 way partition，思路跟 dutch national flag problem 一样。
三个指针遍历，有三种情况， <0, ==0, >0，然后根据情况进行 swapping。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g*******i 的大作中提到】
: 给一个整数的ARRAY,有正有负有零，要求inplace变成先负数再零再正数(负数和正数内
: 部顺序不能
: 变)。
|
g*******i
发帖数: 95 | 3 如何保证负数内部和正数内部还是原来的顺序？
Dutch national flag problem是不区分元素顺序的
这是stackoverflow上的讨论：
http://stackoverflow.com/questions/5347616/how-to-sort-an-integ |
f*****w
发帖数: 2602 | 4 同问 我也觉得3partition 好像不能保证顺序 |
i**********e
发帖数: 1145 | 5 恩，说得对，的确不能保证保持原有顺序。
那这样呢，假设三个 index 为 lo, mid, hi，并且同时满足以下条件：
A[i] < 0, All i < lo
A[j] == 0, i <= j < mid
A[k] > 0, mid <= k < hi
当 A[hi] 与 A[mid] 交换了之后，就把 A[mid+1] 到 A[hi-1] 往上移一步， 再把原
来的 A[hi] 插入 A[mid+1] 的位置就好。这样能保证原有顺序。
至于最坏情况的复杂度呢，是否 O(N^2) 还有待验证。也有可能 amortized O(N) run
time.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 g*******i 的大作中提到】
: 如何保证负数内部和正数内部还是原来的顺序？
: Dutch national flag problem是不区分元素顺序的
: 这是stackoverflow上的讨论：
: http://stackoverflow.com/questions/5347616/how-to-sort-an-integ
|
b**********r
发帖数: 91 | 6 partition by 0 and then partition by 1
It scans twice.
Dutch flag sort is not stable. The other way is american flag sort, but it
takes two scans as well.
【在 g*******i 的大作中提到】
: 给一个整数的ARRAY,有正有负有零，要求inplace变成先负数再零再正数(负数和正数内
: 部顺序不能
: 变)。
|
g*******i
发帖数: 95 | 7 partition by 0怎么保持顺序呢
能说具体点么
it
【在 b**********r 的大作中提到】
: partition by 0 and then partition by 1
: It scans twice.
: Dutch flag sort is not stable. The other way is american flag sort, but it
: takes two scans as well.
|
f****4
发帖数: 1359 | 8 x1 x2 x3 y1 z1 y2 x4 y3 z2 z3
xi<0; yi=0; z1>0
i指向x3， j指向x4
交换y2,x4
交换z1,x4
交换y1,x4
i指向x4, j指向y3
partition 0之后可以用i+1到数组结尾调用partition 1(如果数组是整数的话)
可能是O(n^2)
【在 g*******i 的大作中提到】
: partition by 0怎么保持顺序呢
: 能说具体点么
:
: it
|
d*******l
发帖数: 338 | 9 这个如果小于零的全在最后，大于零的全在最前，应该就是最朴素的O(n^2)，跟插入排
序的过程有点像
【在 f****4 的大作中提到】
: x1 x2 x3 y1 z1 y2 x4 y3 z2 z3
: xi<0; yi=0; z1>0
: i指向x3， j指向x4
: 交换y2,x4
: 交换z1,x4
: 交换y1,x4
: i指向x4, j指向y3
: partition 0之后可以用i+1到数组结尾调用partition 1(如果数组是整数的话)
: 可能是O(n^2)
|
i**********e
发帖数: 1145 | 10 不好意思，我之前的解答没考虑到还要对 ==0 的也进行数组移位。虽然 DNF 可以改进
来保持顺序，但由于数组移位的关系，复杂度肯定是 O(N^2)。那还不如用 insertion
sort. 感觉不可能会有 O(N) 的 in-place partition 并且保证顺序。唯一一个办法就
是用链表，那就能保证 O(N)。
我在网上找了找，应该就是这题啊，题目也没要求要保持顺序：
http://www.glassdoor.com/Interview/Partition-an-array-in-such-w
还有，另一点是这题也曾在 Programming pearls 出现过。在 Column 11 的第 11 条
练习题。这个 3-way partition 可是应用于 quicksort 里的。可以在网上搜 3-way
quicksort partition。quicksort 也不是 stable sort。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
|
s**********k
发帖数: 934 | 11 similar to bubble sort.
only difference is swap 相邻两个元素
if ( a[j] > a[j+1] && a[j]*a[j+1] <= 0)
【在 g*******i 的大作中提到】
: 给一个整数的ARRAY,有正有负有零，要求inplace变成先负数再零再正数(负数和正数内
: 部顺序不能
: 变)。
|
g*******i
发帖数: 95 | 12 我有一个思路，是不是可以用类似于MergeSort的方法递归达到O(nlogn)
合并相邻的两个处理过的数列比如
x1,x2,x3,y,y,z1,z2,z3, 和 X1,X2,Y,Z1,Z2 (xi<0,y==0,z>0)
（1）反转z1到X2
（2）反转X1到X2，反转z1到z3
(3) 移动X1,X2到x3后，移动z1,z2,z3到Z1前，当中元素改为y==0
大家觉得有什么问题么？ |
g***s
发帖数: 3811 | 13 since we dont care the stablility of 0, so, we can use the 0 to adjust.
if the (number of 0) / (number of array) is a constant level, it can be
solved by O(n).
assum number of 0 is k
1. Partition (or compact,or something like inplace delete) to non-0 and 0 O
(n)
2. check if number of position < number of negative. pick smaller one to do
3-5. assume we choose positive number.
3. scan from end, non-0 number;
4. swap k position number with 0s
5. compact 0, go to 4, util all positive numbers are moved to the end.
6. compact 0 with negtive numbers.
e.g.
9 -3 0 2 -7 -1 5 -4 3 0 -6
1. -> 9 -3 2 -7 -1 5 -4 3 -6 0 0
-> 9 -3 2 -7 -1 0 -4 0 -6 5 3
-> 9 -3 2 -7 -1 0 -4 0 -6 5 3
-> 9 -3 2 -7 -1 -4 -6 0 0 5 3
-> 0 -3 0 -7 -1 -4 -6 9 2 5 3
-> -3 -7 -1 -4 -6 0 0 9 2 5 3 |
g**e
发帖数: 6127 | 14 mark
O
do
【在 g***s 的大作中提到】
: since we dont care the stablility of 0, so, we can use the 0 to adjust.
: if the (number of 0) / (number of array) is a constant level, it can be
: solved by O(n).
: assum number of 0 is k
: 1. Partition (or compact,or something like inplace delete) to non-0 and 0 O
: (n)
: 2. check if number of position < number of negative. pick smaller one to do
: 3-5. assume we choose positive number.
: 3. scan from end, non-0 number;
: 4. swap k position number with 0s
|
f****4
发帖数: 1359 | 15 这个方法好
if the (number of 0) / (number of array) is a constant level, it can be
solved by O(n)么？
是不是你这里假设如果 (number of 0) = (length of array)/k , k>=1是constant
value？
如果前面的假设理解对的话，(number of 0) / (length of array) -> 0的话还是O(n^
2)?
考虑数组 2n+1长度
n个大于零的数在前 0 n个小于零的数在后面
每次只能移动1个大于零的数到数组后部，需要移动n个小于零的数
O
do
【在 g***s 的大作中提到】
: since we dont care the stablility of 0, so, we can use the 0 to adjust.
: if the (number of 0) / (number of array) is a constant level, it can be
: solved by O(n).
: assum number of 0 is k
: 1. Partition (or compact,or something like inplace delete) to non-0 and 0 O
: (n)
: 2. check if number of position < number of negative. pick smaller one to do
: 3-5. assume we choose positive number.
: 3. scan from end, non-0 number;
: 4. swap k position number with 0s
|
t******g
发帖数: 252 | 16 Is this O(n)? The "compact 0" is not constant time.
O
do
【在 g***s 的大作中提到】
: since we dont care the stablility of 0, so, we can use the 0 to adjust.
: if the (number of 0) / (number of array) is a constant level, it can be
: solved by O(n).
: assum number of 0 is k
: 1. Partition (or compact,or something like inplace delete) to non-0 and 0 O
: (n)
: 2. check if number of position < number of negative. pick smaller one to do
: 3-5. assume we choose positive number.
: 3. scan from end, non-0 number;
: 4. swap k position number with 0s
|
g***s
发帖数: 3811 | 17 Yes. e.g. there is no 0.
otherwise, maybe we can use in-place merge which is used in stl
stable_sort().
n^
【在 f****4 的大作中提到】
: 这个方法好
: if the (number of 0) / (number of array) is a constant level, it can be
: solved by O(n)么？
: 是不是你这里假设如果 (number of 0) = (length of array)/k , k>=1是constant
: value？
: 如果前面的假设理解对的话，(number of 0) / (length of array) -> 0的话还是O(n^
: 2)?
: 考虑数组 2n+1长度
: n个大于零的数在前 0 n个小于零的数在后面
: 每次只能移动1个大于零的数到数组后部，需要移动n个小于零的数
|
g***s
发帖数: 3811 | 18 Compact 0 is O(n). Just like in-place delete.
We only need to do n/k times. based on my assumption, it is a const.
【在 t******g 的大作中提到】
: Is this O(n)? The "compact 0" is not constant time.
:
: O
: do
|
t******g
发帖数: 252 | 19 What's wrong with a simple insertion sort? Treat all negatives as equal and
all positives as equals also. |
g***s
发帖数: 3811 | 20 Time concern. in-place merge sort is better.
and
【在 t******g 的大作中提到】
: What's wrong with a simple insertion sort? Treat all negatives as equal and
: all positives as equals also.
|
|
|
t******g
发帖数: 252 | 21 That's right. How many times do you have to compact?
【在 g***s 的大作中提到】
: Compact 0 is O(n). Just like in-place delete.
: We only need to do n/k times. based on my assumption, it is a const.
|
m**q
发帖数: 189 | 22 学习了
0 O
do
【在 g***s 的大作中提到】
: since we dont care the stablility of 0, so, we can use the 0 to adjust.
: if the (number of 0) / (number of array) is a constant level, it can be
: solved by O(n).
: assum number of 0 is k
: 1. Partition (or compact,or something like inplace delete) to non-0 and 0 O
: (n)
: 2. check if number of position < number of negative. pick smaller one to do
: 3-5. assume we choose positive number.
: 3. scan from end, non-0 number;
: 4. swap k position number with 0s
|
g***s
发帖数: 3811 | 23 n/k times
【在 t******g 的大作中提到】
: That's right. How many times do you have to compact?
|
t******g
发帖数: 252 | 24 I see. You're changing the question.
If k/n is constant, do you have to compact 0 to benefit?
【在 g***s 的大作中提到】
: n/k times
|
t******g
发帖数: 252 | 25 I see what's going on here. If there is no requirement of in-place for this
question, then it's very simple. By requiring constant portion of 0 in the
array, you actually gain space to get over the in-place hurdle.
【在 m**q 的大作中提到】
: 学习了
:
: 0 O
: do
|
g***s
发帖数: 3811 | 26 or do you have better solution? My solution is just using the k 0s as a
extra space. I mentioned in another post, if k<
be used.
【在 t******g 的大作中提到】
: I see. You're changing the question.
: If k/n is constant, do you have to compact 0 to benefit?
|
f****4
发帖数: 1359 | 27 能说说in-place操作，到底是怎么要求的么？
比如说，当两个数交换的时候，给不给用temp变量啊？
【在 g***s 的大作中提到】
: or do you have better solution? My solution is just using the k 0s as a
: extra space. I mentioned in another post, if k<: be used.
|
g***s
发帖数: 3811 | 28 In-place means using O(1) space. temp is needed.
【在 f****4 的大作中提到】
: 能说说in-place操作，到底是怎么要求的么？
: 比如说，当两个数交换的时候，给不给用temp变量啊？
|
f****4
发帖数: 1359 | 29 多谢
【在 g***s 的大作中提到】
: In-place means using O(1) space. temp is needed.
|
