合并数组
合并数组
http://www.nowcoder.com/questionTerminal/20c8731629b64109825595c3d349d2fc
题目难度：一星
考察点：合并两个有序数组
方法：合并两个有序数组
1. 分析：
题目的意思就是给定两个有序数组，然后将这两个有序数组进行排序，然后输出，但是不能使用c++内部自定义的sort函数等等。其实这个跟归并排序的想法是差不多的，首先我们假设两个有序数组a和b，长度分别为n和m，那么我们可以创建一个新的数组ans用来保存排序之后的数组，那么我们具体的想法就是定义两个指针i=0和j=0，i指针代表遍历的是a数组，j指针代表遍历的是b数组，然后我们比较a[j]和b[j]，然后把小的那个放在ans数组种。具体表现形式为:if(a[i] < b[j]) ans[k++] = a[i++];
else ans[k++] = b[j++];
然后当某一个数组比完之后，直接把另外一个数组的值赋给ans即可。
举个例子:
a数组为[1, 4]
b数组为[2, 3]
第一步：a[0]和b[0]比，那么显然a[0]小，所以ans[0] = a[0] = 1;
第二步：a[1]和b[0]比，那么显然b[0]小，所以ans[1] = b[0] = 2;
第三步：a[1]和b[1]比，那么显然b[1]小，所以ans[2] = a[1] = 3;
第四步：剩下一个a[1]，直接赋值，所以ans[3] = a[1] = 4;
所以排序之后的数组为ans=[1, 2, 3, 4]
tips：
(1). 这个题的输入是比较恶心的，首先要处理一下输入，将字符串转化为数组，在这里我采用vector实现。
(2). 还有一个坑点就是如果这两个字符串其中有一个是空串的话，直接输出另外一个字符串即可，没有必要去转化为数组。
算法实现：
(1). 首先输入两个字符串。
(2). 写一个将字符串转化为vector的函数，在代码中叫做get_array，返回值为vector。
(3). 得到两个数组a和b，之后按照上述的方法进行比较排序。
(4). 输出两个数组排序之后的结果。
2. 复杂度分析：
时间复杂度：O(n+m)空间复杂度：O(n+m)
3. 代码：
#include <bits/stdc++.h>
using namespace std;
vector<int> get_array(string s) {
vector<int> ans;
int num = 0;
for(int i=0; i<s.size(); i++) {
if(s[i] == ',') {
ans.push_back(num);
num = 0;
}
else num = num*10+s[i]-'0';
}
ans.push_back(num);
return ans;
}
int main() {
string s1, s2; cin>>s1>>s2;
if(s1 == "") {
cout<<s2<<endl;
return 0;
}
if(s2 == "") {
cout<<s1<<endl;
return 0;
}
vector<int> a = get_array(s1);
vector<int> b = get_array(s2);
vector<int> ans;
int i = 0, j = 0;
while(i<a.size() && j<b.size()) {
if(a[i] < b[j]) ans.push_back(a[i++]);
else ans.push_back(b[j++]);
}
while(i < a.size()) ans.push_back(a[i++]);
while(j < b.size()) ans.push_back(b[j++]);
for(int i=0; i<ans.size(); i++) {
if(i == ans.size()-1) cout<<ans[i];
else cout<<ans[i]<<",";
}
return 0;
}
查看21道真题和解析
