面试金典--11.1

题目描述：给定排序后数组A和B，其中A的末端有足够空间存B，编写算法，将B合并到A

思路：

题目的意思应该是不用额外空间，所以从两个数组的最后一个元素往前遍历，将大的放入A的末尾

 1 #include <iostream>
 2 #include <queue>
 3 #include <climits>
 4 #include <algorithm>
 5 #include <memory.h>
 6 #include <stdio.h>
 7 using namespace std;
 8 
 9 vector<int> fun(vector<int> a,vector<int> b,int na,int nb)
10 {
11     int lena = a.size();
12     int lenb = b.size();
13 
14     int i,j;
15     int k = lena-1;
16     for(i = na-1,j = nb-1 ; i >=0 && j >=0 ;)
17     {
18         if(a[i] >= b[j])
19         {
20             a[k] = a[i];
21             --i;
22             --k;
23         }
24         else
25         {
26             a[k] = b[j];
27             --j;
28             --k;
29         }
30     }
31     if(i < 0)
32     {
33         while(j >= 0)
34         {
35             a[k] = b[j];
36             --j;
37             --k;
38         }
39     }
40     return a;
41 }
42 
43 int main()
44 {
45     vector<int> a;
46     a.push_back(1);
47     a.push_back(2);
48     a.push_back(3);
49     a.push_back(2);
50     a.push_back(2);
51     sort(a.begin(),a.end());
52     a.push_back(0);
53 
54     vector<int> b;
55     b.push_back(4);
56 
57     vector<int> res = fun(a,b,5,1);
58     int i;
59     for(i = res.size()-1 ; i >=0 ; --i )
60     {
61         cout<<res[i]<<endl;
62     }
63     return 0;
64 }