已知数组A和B各有m、n个元素,且元素按值非递减排列,现要求把A和B归并为一个新的数组C,且C中的数据元素仍然按值非递减排列。 例如,若A=(3,5,8,11),B=(2,6,8,9,11,15,20), 则C=(2,3,5,6,8,8,9,11,11,15,20c++
时间: 2023-10-12 08:04:37 浏览: 106
这个问题可以用归并排序的思想来解决。具体步骤如下:
1. 定义一个新数组C,长度为m+n。
2. 定义三个指针:pA指向数组A的第一个元素,pB指向数组B的第一个元素,pC指向数组C的第一个元素。
3. 依次比较pA和pB所指向的元素大小,将较小的元素放入数组C中,并且移动对应的指针。
4. 当其中一个数组的元素全部被放入数组C中后,将另一个数组剩余的元素依次放入数组C中。
5. 返回数组C。
以下是C++代码实现:
```
#include <iostream>
using namespace std;
int* merge(int A[], int B[], int m, int n) {
int* C = new int[m + n];
int pA = 0, pB = 0, pC = 0;
while (pA < m && pB < n) {
if (A[pA] <= B[pB]) {
C[pC++] = A[pA++];
} else {
C[pC++] = B[pB++];
}
}
while (pA < m) {
C[pC++] = A[pA++];
}
while (pB < n) {
C[pC++] = B[pB++];
}
return C;
}
int main() {
int A[] = {3, 5, 8, 11};
int B[] = {2, 6, 8, 9, 11, 15, 20};
int* C = merge(A, B, 4, 7);
for (int i = 0; i < 11; i++) {
cout << C[i] << " ";
}
delete[] C; // 注意释放内存
return 0;
}
```