合并两个有序数组，要求时间复杂度为O(n),空间复杂度为O(1)
合并两个有序数组，要求时间复杂度为O(n),空间复杂度为O(1)
lexingsen
发布于 2022-02-24 20:15:56
发布于 2022-02-24 20:15:56
思路：因为数组已经是有序的，因此我们可以直接从两个数组的末位开始比较，将大的一个直接放到第一个数组的末尾，此时必须要求a数组的空间大小能够同时填充a数组和b数组的有效元素，然后依次比较两个数组元素的大小即可。
代码实现：
#include <bits/stdc++.h>
void merge(int *a, int n, int *b, int m) {
int i = n-1;//a数组的最后一个有效元素的下标
int j = m-1;//b数组的最后一个有效元素的下标
int index = n+m-1; //合并数组的最后一位的下标
while (index) {
if (i && a[i]>a[j]) a[index --] = a[i --];
else a[index --] = b[j --];
}
}
int main() {
int a[] = {1,3,5,7,9,0,0,0,0,0};
int n = sizeof(a)/sizeof(int);
int b[] = {2,4,6,8,10};
int m = sizeof(b)/sizeof(int);
merge(a, 5, b, m);
for_each(a, a+n, [](int x) {cout << x << " ";});
return 0;
}本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读