m******9 发帖数: 968 | 1 有个关于inplace merge的题目没想明白:
two sorted arrays A and B,size 分别为m和n,需要in place merge它们,不能用
extra space
一个常见的题目是:A中有足够的空间可以另外容纳下整个B。这个题目可以用的方法是
: 用merge sort中merge的办法,都从A和B的最后一个元素开始往前scan,A[i] B[j]
哪个大,就将大的放置在A的尾端,下次比较将大的放置在次尾端,依次进行下去。O(m+n)
比如:
A: 1 3 5 _ _ _ _
B: 2 4 6 8
output: A: 1 2 3 4 5 6 8
但是另外一个变形的题目是: A就是A,没有另外的空间可以容纳B。
即:
A: 1 3 5
B: 2 4 6 8
结果应当是:
A: 1 2 3
B: 4 5 6 8
我知道的一个方法是利用selection sort的思想,每次都从A B中select一个min放在最
左端,然后下次选择sec min放在次左端,依次下去。O(n^2)
这种题目,大家有什么好办法吗? 谢了 |
m******9 发帖数: 968 | |
l***i 发帖数: 1309 | 3 For your second problem, why not dump the smallest numbers to A and the rest
to B(swap max in A with min in B), then sort A, B separately to get O(nlogn
). Heap sort can do this since you do not have O(n) extra storage. |
g*******y 发帖数: 1930 | 4 分冶可以做到nlogn的in place merge
简单说就是在B中binary 搜索A的median的位置,然后交换两段,然后分冶
不过肯定不是最优了,不过我觉得对于面试的要求也许还行。
(m+n)
【在 m******9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 有个关于inplace merge的题目没想明白: : two sorted arrays A and B,size 分别为m和n,需要in place merge它们,不能用 : extra space : 一个常见的题目是:A中有足够的空间可以另外容纳下整个B。这个题目可以用的方法是 : : 用merge sort中merge的办法,都从A和B的最后一个元素开始往前scan,A[i] B[j] : 哪个大,就将大的放置在A的尾端,下次比较将大的放置在次尾端,依次进行下去。O(m+n) : 比如: : A: 1 3 5 _ _ _ _ : B: 2 4 6 8 : output: A: 1 2 3 4 5 6 8
|
l**s 发帖数: 50 | 5 quick sort nlogn
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 分冶可以做到nlogn的in place merge : 简单说就是在B中binary 搜索A的median的位置,然后交换两段,然后分冶 : 不过肯定不是最优了,不过我觉得对于面试的要求也许还行。 : : (m+n)
|
g*******y 发帖数: 1930 | 6 yes,
but, then, what's point of the problem?
I don't think this is a good interview problem after all.
【在 l**s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : quick sort nlogn
|
m******9 发帖数: 968 | 7 先用scan的方法,比如用2 pointer都从A B的左端开始scan,将smaller numbers都
swap到A
中,然后再sort B,例如用heap sort, quick sort
整体上是O(nlgn)
rest
O(nlogn
【在 l***i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : For your second problem, why not dump the smallest numbers to A and the rest : to B(swap max in A with min in B), then sort A, B separately to get O(nlogn : ). Heap sort can do this since you do not have O(n) extra storage.
|
m******9 发帖数: 968 | 8 小尾羊,能再具体一下吗?我没跟上你的思路,尤其是“交换两段”那部分?
多谢
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 分冶可以做到nlogn的in place merge : 简单说就是在B中binary 搜索A的median的位置,然后交换两段,然后分冶 : 不过肯定不是最优了,不过我觉得对于面试的要求也许还行。 : : (m+n)
|