给出一个整数数组 和有序的整数数组 ,请将数组 合并到数组 中,变成一个有序的升序数组
注意:
1.可以假设 数组有足够的空间存放 数组的元素, 和 中初始的元素数目分别为 和 ,的数组空间大小为 +
注意:
1.可以假设 数组有足够的空间存放 数组的元素, 和 中初始的元素数目分别为 和 ,的数组空间大小为 +
2.不要返回合并的数组,返回是空的,将数组 的数据合并到里面就好了
3.数组在[0,m-1]的范围也是有序的
例1:
A: [1,2,3,0,0,0],m=3
B: [2,5,6],n=3
合并过后A为:
A: [1,2,2,3,5,6]
解题思路:
将两个数组a、b中较小的一个依次丢入第三个数组c中,再将数组c拷贝到数组a
class Solution { public: void merge(int A[], int m, int B[], int n) { int i=0,j=0,p=0; int c[m+n];//定义辅助数组C while(i<m&&j<n){ c[p++]=A[i]<=B[j]?A[i++]:B[j++];//将A[i]和B[j]中小的那个丢入C中 } while(i<m){//如果A中有剩余 c[p++]=A[i++]; } while(j<n){//如果B中有剩余 c[p++]=B[j++]; } for(int i=0;i<p;i++)A[i]=c[i];//因为题目要求,将C数组拷贝到A数组中 } };
全部评论
(1) 回帖