非递减序列排序 通过容器展示 进行暴力排序放入新容器中_干饭人小龙的博客-爱代码爱编程
目录
题目：
写一个函数，传入两个非降序的整数数组（A, B），将 A, B 合并成一个非降序数组 C，返回 C
（不要使用内置 sort 函数）。
分析：
1.对于给予我们的主函数，可以发现要写的函数 solution(n, m, num1, num2)返回值是一个vector<int>的容器，并且四个参数里有两个vector<string>的容器，那么首先我们是要进行容器中数据的类型转换，将string转换成int类型，方便我们后续操作；
2.组成的非降序数组C，应该要满足什么要求嘞，会需要将相同的整数合并吗？还是继承前两个数组一样，非降序那么就有可能在整个容器中全是一样的数，那么就可以了解到我最后要得到的数组应该是什么样子的；
3.知道最后要得到的容器里的数据是什么样的，那我们只需要对两个容器中的数据进行对比判断就行，c++中的容器操作是可以像数组一样，通过数组下标索引指定对应的值，不断进行对比操作小的放入新容器中，直到两个容器的下标都等于长度（循环临界值）。
int main()
int n;
int m;
std::vector<std::string> num1;
std::vector<std::string> num2;std::cin>>n;
std::cin>>m;std::string line_0, token_0;
getline(std::cin >> std::ws,line_0);
std::stringstream tokens_0(line_0);
while(std::getline(tokens_0, token_0, ' ')){
num1.push_back((token_0));
}
std::string line_1, token_1;
getline(std::cin >> std::ws,line_1);
std::stringstream tokens_1(line_1);
while(std::getline(tokens_1, token_1, ' ')){
num2.push_back((token_1));
}
std::vector<int> result = solution(n, m, num1, num2);
for(auto it=result.begin();it!=result.end();++it){
std::cout<<*it<<" ";
}
std::cout<<std::endl;
return 0;
}
编写代码：
1.首先进行的容器内的数据转换；
通过transform函数以Tolnt表达式，进行容器中数据的转换。（改变容器中的大小写也是通过这种办法）
back_inserter()定义在头文件iterator中。接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器，通过此迭代器赋值会调用push_back添加元素到容器。
int ToInt(const string &str)
{
return atoi(str.c_str()); //将String类型转成int类型
}
std::vector<int> solution(int n, int m, vector<std::string>& num1, vector<std::string>& num2){
std::vector<int> result;
std::vector<int> num3;
std::vector<int> num4;
//transform不自动分配内存的。
std::transform( num1.begin(), num1.end(), std::back_inserter(num3), ToInt); std::transform( num2.begin(), num2.end(), std::back_inserter(num4), ToInt);
2.对转换int类型的数据进行对比分析，放入 ，当时写的时候采用的暴力放入，没有啥技巧；
首先要创建得到两个index索引值，清楚现在对比的是哪两个数，设置i索引容器num3（0<=i<n)，j索引num4(0<=j<m)，遍历对比数据；
（1）对于第一种情况，先开始索引的值num3[i]小于num4[j]，那么就说明放入目标容器中的数应该是num3[i]，直接通过push_back()函数进行放入，随后就要使i自增，因为i的循环在外层，此时的循环是j，所以得跳出当前j的循环，使用break；完成num3下一个数与num4现在的数进行比较； 极限情况：在外部的循环i以及不满足i<n了，但是j都还没有一次自增，也就是num3里的数全部比num4小怎么办？ 在这个if判断里面加入一个针对索引j的循环，进入的条件就是i==（n-1），也就是num3以及全部放入了目标容器中，那么num4按顺序放入之后的目标容器即可；
if (num3[i]<num4[j])
{
//将num3小的放入
result1.push_back(num3[i]);
//如果num3很多都比num4小 将num3放进去完之后 i=n-1 最后一个时
//将大的num4全部放入
if (i==(n-1))
{
for (;j<m;j++)
{
result1.push_back(num4[j]);
}
//break跳出循环时 j=m
}
break;
}
（2） 如果num3[i]大于num4[j]，那么将num4[j]放入目标容器后，利用continue直接结束后面的判断，完成j的自增，进行下一轮的对比；当然这里也会有一种极限情况：num3中的全部大于num4中的，不过不需要在这个内循环里进行操作，可以在外循环i的自增循环中在进行数据的放入；
（3）第三种情况就是num3[i]等于num4[j]，那么这两个都放入，i和j都自增，去完成下两个数的对比，因为内循环是j的，通过break跳出是没有实现j自增的，所以需要在break之前完成j++；极限情况：因为这么break出j的循环后，完成i++；并要进行i<n的对比，那么如果num3的最后一个数与num4中的某一个数相等，再跳出去i++后，不满足i<n了，就会导致mun4中的某些数据没有放入，所以要应对这种情况，跟第一种方法一样；
if (num3[i]==num4[j])
{
//相等时 目标容器放入num3的数 同时j++，并跳出当前for 使得i也+1
result1.push_back(num3[i]);
result1.push_back(num4[j]);
j++;
//if(j==m)
// i++;//后面判断时还没来得及后移下一位 会导致多输出一次
//当num3最后一个数与num4中间的数相等 num4中还有很多数据
if (i==(n-1))
{
for (;j<m;j++)
{
result1.push_back(num4[j]);
}
}
break;
}
总体的代码：
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
int ToInt(const string &str)
{
return atoi(str.c_str()); //将String类型转成int类型
}
std::vector<int> solution(int n, int m, std::vector<std::string>& num1, std::vector<std::string>& num2){
std::vector<int> num3;
std::vector<int> num4;
//transform不自动分配内存的。
std::transform( num1.begin(), num1.end(), std::back_inserter(num3), ToInt);
std::transform( num2.begin(), num2.end(), std::back_inserter(num4), ToInt);
int i=0;
int j=0;
std::vector<int> result1;
for (i=0,j=0;i<n;i++)
{
for (;j<m;j++)
{
//当前的num3小于num4
if (num3[i]<num4[j])
{
//将num3小的放入
result1.push_back(num3[i]);
//如果num3很多都比num4小 将num3放进去完之后 i=n-1 最后一个时
//将大的num4全部放入
if (i==(n-1))
{
for (;j<m;j++)
{
result1.push_back(num4[j]);
}
//break跳出循环时 j=m
}
break;
}
//num3当前的数据比num4大
if (num3[i]>num4[j])
{
//将小的num4放入目标容器中
result1.push_back(num4[j]);
//继续下一个num4与现在的这个num3对比
continue;
}
if (num3[i]==num4[j])
{
//相等时 目标容器放入num3的数 同时j++，并跳出当前for 使得i也+1
result1.push_back(num3[i]);
result1.push_back(num4[j]);
j++;
//if(j==m)
// i++;//后面判断时还没来得及后移下一位 会导致多输出一次
//当num3最后一个数与num4中间的数相等 num4中还有很多数据
if (i==(n-1))
{
for (;j<m;j++)
{
result1.push_back(num4[j]);
}
}
break;
}
}
//当num4里面的数全部放进目标容器
if (j==m)
{
//如果num3[n-1]比num4[m-1]小 就说明前面已经全部放进去
if (num3[n-1]<num4[m-1])
break;
//num3与num4最后一位是一样的 也不用再操作了
else if (num3[n-1]==num4[m-1])
break;
//num3中还有多个数没有读进
else
{
//num3中间的数与num4最后一个相等
for (;i<n;i++)
{
result1.push_back(num3[i]);
}
}
}
}
return result1;
}
int main() {
int n;
int m;
while(1)//加入while循环，方便后续的测试验证，就不用编译一次看一次 注意完成一次后要clear清除容器里的数据，防止数据混乱
{
std::vector<std::string> num1;
std::vector<std::string> num2;
std::cin>>n;
std::cin>>m;
std::string line_0, token_0;
getline(std::cin >> std::ws,line_0);
std::stringstream tokens_0(line_0);
while(std::getline(tokens_0, token_0, ' ')){
num1.push_back((token_0));
}
std::string line_1, token_1;
getline(std::cin >> std::ws,line_1);
std::stringstream tokens_1(line_1);
while(std::getline(tokens_1, token_1, ' ')){
num2.push_back((token_1));
}
std::vector<int> result = solution(n, m, num1, num2);
for(auto it=result.begin();it!=result.end();++it){
std::cout<<*it<<" ";
}
std::cout<<std::endl;
num1.clear();
num2.clear();
result.clear();
}
system("pause");
return 0;
}测试结果：
