题目描述
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.
题目大意
给定两个排序的整型数组A和B，将B合并到A中。
假设A有足够的空间来容纳B中的元素，A和B中初始的元素数目分别为m和n。
思路
最优解：从后往前处理,不需要开辟额外空间。
i从A的末尾，j从B末尾开始，两两比较，大的放在末端。
如此类推如果A穷尽，把B元素依次放进A的前几个位置（第二个while循环），如果B穷尽，正好结束（此时不用判断）。
代码
#include<iostream>
using namespace std;
void merge(int A[], int m, int B[], int n)
{
int i = m-1, j = n-1, index = m+n-1;
// 当A和B都没有遍历完
while(i>=0 && j>=0)
{
// 大的放到当前index位置
A[index--] = A[i]>B[j] ? A[i--]:B[j--];
}
// 当B没有遍历结束时，直接把B剩余元素放进A
// A未穷尽时不用判断，直接就在前边了
while(j >= 0)
{
A[index--] = B[j--];
}
}
int main()
{
int A[10] = {1, 3, 5, 7, 9};
int B[] = {2, 4, 6, 8, 10};
merge(A, 5, B, 5);
for(int i=0; i<10; i++)
{
cout<<A[i]<<' ';
}
cout<<endl;
return 0;
}
运行结果
以上。
