2014-05-02 07:37
原题：
// merge sorted arrays 'a' and 'b', each with 'length' elements,
// in-place into 'b' to form a sorted result. assume that 'b'
// has 2*length allocated space.
// e.g. a = [1, 3, 5], b = [2, 4, 6] => b = [1, 2, 3, 4, 5, 6] //how to do it without rearanging the b array
题目：有两个排好序的数组a[]和b[]，把a有序归并到b中去，保证b的空间充足。如何就地完成这个算法？
解法：从后往前归并就可以不用额外空间了。
代码：
// http://www.careercup.com/question?id=5435439490007040
#include <iostream>
#include <vector>
using namespace std; class Solution {
public:
void mergeTwoArray (vector<int> &a, vector<int> &b) {
// merge a[] into b[].
int na = (int)a.size();
int nb = (int)b.size(); b.resize(na + nb); int i, j, k; i = na - ;
j = nb - ;
k = na + nb - ;
while (i >= && j >= ) {
b[k--] = a[i] > b[j] ? a[i--] : b[j--];
}
while (i >= ) {
b[k--] = a[i--];
}
};
}; int main()
{
vector<int> a, b;
int na, nb;
int i;
Solution sol; while (cin >> na >> nb && (na > && nb > )) {
a.resize(na);
b.resize(nb);
for (i = ; i < na; ++i) {
cin >> a[i];
}
for (i = ; i < nb; ++i) {
cin >> b[i];
}
sol.mergeTwoArray(a, b);
nb = (int)b.size();
for (i = ; i < nb; ++i) {
i ? (cout << ' ', ) : ;
cout << b[i];
}
cout << endl; a.clear();
b.clear();
} return ;
}