题解 | #合并两个有序的数组#
合并两个有序的数组
http://www.nowcoder.com/practice/89865d4375634fc484f3a24b7fe65665
题目描述：
给出一个整数数组 
和有序的整数数组 
，请将数组 合并到数组 
中，变成一个有序的升序数组
注意：
1.可以假设数组有足够的空间存放 数组的元素， 和 中初始的元素数目分别为 
和 
，的数组空间大小为 +
注意：
1.可以假设
2.不要返回合并的数组，返回是空的，将数组 的数据合并到里面就好了
3.数组在[0,m-1]的范围也是有序的
解法一：暴力法（不推荐）
将B中所有元素直接插入A的尾部，再用选择排序将A中元素从小到大进行排序
class Solution {
public:
void merge(int A[], int m, int B[], int n) {
for(int i=0;i<n;i++)
A[m+i]=B[i];
for(int i=0;i<m+n-1;i++)
for(int j=i+1;j<m+n;j++)
if(A[i]>A[j])
{
int temp=A[i];
A[i]=A[j];
A[j]=temp;
}
}
}; 解法二：倒序插入法 从A与B的尾部开始逐个比较，较大者插入A的尾部，较小者留下继续进行比较，保证所有数据均被插入
class Solution {
public:
void merge(int A[], int m, int B[], int n) {
int temp=m+n-1;
m--;
n--;
while(m>=0&&n>=0)
{
if(A[m]>B[n]) A[temp--]=A[m--];
else A[temp--]=B[n--];
}
while(n>=0) A[temp--]=B[n--];
}
}; 
Momenta公司福利 286人发布
投递快手等公司10个岗位