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 的大作中提到】
: 有个关于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 的大作中提到】
: 分冶可以做到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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 分冶可以做到nlogn的in place merge
: 简单说就是在B中binary 搜索A的median的位置，然后交换两段，然后分冶
: 不过肯定不是最优了，不过我觉得对于面试的要求也许还行。
:
: (m+n)
|
