Careercup - Facebook面试题 - 5435439490007040

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 ;

 }