奇葩同事真是气死我了，大家进来评评理，我怎么会遇到这种人# Working - 上班一族
m*9
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)
这种题目，大家有什么好办法吗？ 谢了
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)
这种题目，大家有什么好办法吗？ 谢了
