首页 > 代码库 > careercup-排序和查找 11.1
careercup-排序和查找 11.1
11.1 给定两个排序后的数组A和B，其中A的末端有足够的缓冲空间容纳B。编写一个方法，将B合并入A并排序。
解法：
已知数组A末端有足够的缓冲，不需要再分配额外空间。程序的处理逻辑很简单，就是逐一比较A和B中的元素，并顺序插入数组，直至耗尽A和B中的所有元素。这么做的唯一问题是，如果将元素插入数组A的前端，就必须将原来的元素往后移动，以腾出空间。更好的做法是将元素插入数组A的末端，那里都是空闲的可用空间。
下面的代码就是实现了上述做法，从数组A和B的末端元素开始，将最大的元素放到数组A的末端。
C++实现代码：
#include<iostream>using namespace std;void merge(int a[],int b[],int lastA,int lastB){ int i=lastA-1; int j=lastB-1; int k=lastA+lastB-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--]; }}int main(){ int a[14]={1,3,5,7,9}; int b[7]={2,4,6,8,10,11,15}; merge(a,b,5,7); for(auto t:a) cout<<t<<‘ ‘; cout<<endl;}
careercup-排序和查找 11.1
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。