|
问题：
给你两个从小到大的数组a，b。在不申请额外空间下，往a填充a和b合并后的排序数组（假设a的空间是足够的）。
第一种方法：
很直觉的思路是，我们采取和归并排序时同样的策略，每次拿出最小的元素放进去即可。但是由于每次渴望拿最小，每填充一个元素后，需要重新维护有个冒泡的过程。
第二种方法：
每次拿a,b最大的元素，好处是省略了维护冒泡的过程，复杂度降低了。
#include <bits/stdc++.h>
using namespace std;
//复杂度O(m*n)
//需要一个冒泡过程
//每次取出a,b最小值
vector<int> alg1(vector<int> a,vector<int> b){
int as = a.size();
a.insert(a.end(),b.begin(),b.end());
int poi = 0;
while(poi<as){
if(a[poi]<a[as])poi++;
else{
swap(a[poi],a[as]);
for(int i = as;i<(int)a.size()-1;i++)if(a[i]>a[i+1])swap(a[i],a[i+1]);
}
}
return a;
}
//复杂度O(n)
//每次取出a,b最大值
vector<int> alg2(vector<int> a,vector<int> b){
int i = a.size()-1;
int j = b.size() - 1;
a.insert(a.end(),b.begin(),b.end());
int k = a.size()-1;
while(i>=0 && j>=0){
if(a[i]>b[j])a[k--] = a[i--];
else a[k--] = b[j--];
}
while(j>=0)a[k--]=b[j--];
return a;
}
int main() {
// interesting
vector<int> a = {5,6,7,8};
vector<int> b = {2,3,9,11,13,45};
vector<int> ret = alg1(a,b); //复杂度O(m*n)
for(auto it:ret)cout<<it<<" ";
cout<<endl;
cout<<"algo 2"<<endl;
ret = alg2(a,b); //复杂度O(n)
for(auto it:ret)cout<<it<<" ";
cout<<endl;
return 0;
}
| 
转播
