简单来说,时间复杂度最低为O(m+n)== m和n指的是两个有序数组的大小
代码实现:
//输出结果
template<class T>
void PrintVecResult(vector<T>& vec)
{
cout << "vector result:" << endl;
int i = 0;
for (i = 0; i < vec.size(); i++)
{
cout << vec[i] << endl;
}
cout << "vec end" << endl;
}
//最快合并两个有序数组
//时间复杂度vec_one.size() + vec_two.size()
template<class T>
vector<T>& MergeVector(vector<T>& vec_one,vector<T>& vec_two)
{
vector<T> vec_merge;
vec_merge.reserve(122); //分配两个数组最大
int i = 0; //for one
int j = 0; // for two
int k = 0;
int v1_count = vec_one.size();
int v2_count = vec_two.size();
int v_merge_count = v1_count+ v2_count;
// int k = 0;
while (i < v1_count && j < v2_count)
{
//如果第一项 小于 第二项
if (vec_one[i] < vec_two[j])
{
vec_merge.push_back(vec_one[i]);
i = i+1;
}
else
{
vec_merge.push_back(vec_two[j]); //从小到大排序
j = j+1;
}
}
//至少会排完一列,剩下判断
while (i < v1_count)
{
vec_merge.push_back(vec_one[i++]);
}
while (j < v2_count)
{
vec_merge.push_back(vec_two[j++]);
}
PrintVecResult(vec_merge);
return vec_merge;
}
- 实例运行
int _tmain(int argc, _TCHAR* argv[])
{
vector<int> mm;
mm.push_back(11);
mm.push_back(12);
mm.push_back(21);
mm.push_back(32);
vector<int> ff;
ff.push_back(1);
ff.push_back(6);
ff.push_back(211);
ff.push_back(322);
MergeVector(mm,ff);
system("pause");
return 0;
}
- 运行结果:
可以看到 两个数组合成一个有序数组,而且时间复杂度最小