c语言实现合并两个有序数组。 将两个非递减的有序数组(顺序表),合并为一个非递减的有序数组。 已知两个数组和它们的长度分别为m和n,将第一个数组长度扩展到m+n,多余位置补0,将第二个数组归并到第一个数组上,合并后的数组不需要额外开辟空间。 要求:算法时间复杂程度O(m+n)
时间: 2024-05-02 15:17:52 浏览: 10
```
void merge(int A[], int m, int B[], int n) {
int i = m-1, j = n-1, k = m+n-1;
while (i >= 0 && j >= 0) {
if (A[i] > B[j]) {
A[k--] = A[i--];
} else {
A[k--] = B[j--];
}
}
while (j >= 0) {
A[k--] = B[j--];
}
}
```
相关问题
c语言代码合并两个有序数组(相同只去一项)
以下是合并两个有序数组的C语言代码,相同的元素只会保留一个:
```c
#include <stdio.h>
void merge(int arr1[], int n1, int arr2[], int n2, int result[]) {
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j]) {
result[k++] = arr1[i++];
} else if (arr1[i] > arr2[j]) {
result[k++] = arr2[j++];
} else {
result[k++] = arr1[i++];
j++;
}
}
while (i < n1) {
result[k++] = arr1[i++];
}
while (j < n2) {
result[k++] = arr2[j++];
}
}
int main() {
int arr1[] = {1, 3, 5, 7, 9};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int arr2[] = {2, 3, 4, 6, 8};
int n2 = sizeof(arr2) / sizeof(arr2[0]);
int result[n1 + n2];
merge(arr1, n1, arr2, n2, result);
for (int i = 0; i < n1 + n2; ++i) {
printf("%d ", result[i]);
}
return 0;
}
```
其中,`merge`函数接受两个有序数组`arr1`和`arr2`,分别有`n1`和`n2`个元素,将它们合并到`result`中,并保证合并后的数组仍然有序。在合并过程中,如果两个数组中有相同的元素,只会保留一个。`main`函数演示了如何调用`merge`函数来合并两个有序数组。
C语言合并两个有序数组
对于合并两个有序数组的问题,可以使用双指针法来解决。具体步骤如下:
1. 初始化两个指针p1和p2,分别指向两个有序数组的首元素地址。
2. 比较两个指针所指向的元素大小,若p1指向的元素小,则将该元素输出并将p1指向下一个元素;反之,将p2指向的元素输出并将p2指向下一个元素。
3. 重复步骤2,直到其中一个数组遍历完毕。
4. 将剩余数组中的元素输出。
下面是C语言的示例代码:
```c
#include <stdio.h>
void mergeArrays(int arr1[], int arr2[], int len_arr1, int len_arr2) {
int i = 0, j = 0;
while (i < len_arr1 && j < len_arr2) {
if (arr1[i] <= arr2[j]) {
printf("%d ", arr1[i]);
i++;
} else {
printf("%d ", arr2[j]);
j++;
}
}
// 输出剩余的元素
for (; i < len_arr1; i++) {
printf("%d ", arr1[i]);
}
for (; j < len_arr2; j++) {
printf("%d ", arr2[j]);
}
}
int main() {
int arr1[] = {1, 3, 5, 7, 9, 10, 13, 15};
int arr2[] = {2, 4, 6, 8, 10};
int len_arr1 = sizeof(arr1) / sizeof(arr1[0]);
int len_arr2 = sizeof(arr2) / sizeof(arr2[0]);
mergeArrays(arr1, arr2, len_arr1, len_arr2);
return 0;
}
```
在上述代码中,我们先定义了一个`mergeArrays`函数来合并两个有序数组。然后在`main`函数中,我们定义了两个有序数组`arr1`和`arr2`,并分别计算了它们的长度。最后,调用`mergeArrays`函数来合并并输出结果。