C算法--合并两个有序数组
# 第一：题目描述
1. 将两个整型且有序的数组，合并为一个新的数组。
2. 合并后的数组仍为有序数组。
3. 第一个数组有足够的空间来存放第二个数组。
4. 要求时间复杂度为O(M+N)
# 第二：思路
1. 用malloc函数开辟一个两个数组总长度的连续空间arr
2. 从第一个元素开始，依次比较两个数组中的每个元素。
3. 将较小值保存到新开辟的数组中
4. 并将较小值对应数组的当前索引向后移动一个元素，同时将开辟数组的索引也向后移动一个元素。
5. 这样只需要对每个数组遍历一遍即可，即时间复杂度为O(M+N)，空间复杂度为O(M+N)，即用空间换时间的策略。
# 第三：代码实现
```
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
// 如果第一个数组的长度为0，则直接将第二个数组拷贝到第一个数组中去
if (m == 0)
{
while (n--)
{
nums1[n] = nums2[n];
}
return;
}
// 动态开辟一个两个数组总元素个数 * int的内存空间
int* arr = (int*)malloc(sizeof(int) * (m + n));
if (NULL == arr)
{
printf("内存开辟失败\n");
return;
}
// i j k 分别为第一个、第二个、开辟动态数组的索引
int i = 0, j = 0, k = 0;
// 从第一个和第二个数组的第一个位置开始遍历
// 依次比较两个数组当前索引的两个值的大小，将较小值保存到第三个数组中。
// 将较小值对应的索引和第三个数组的索引向后移动一个元素。
// 直到第一和第二个数组中有一个超出输出索引范围。
while (i < m && j < n)
{
if (nums1[i] < nums2[j])
{
arr[k] = nums1[i];
i++;
}
else
{
arr[k] = nums2[j];
j++;
}
k++;
}
// 第一个数组没有遍历完。
while (i < m)
{
arr[k] = nums1[i];
k++;
i++;
}
// 第二个数组没有遍历完。
while (j < n)
{
arr[k] = nums2[j];
k++;
j++;
}
// 将第三个数组的数据拷贝到第一个数组中
while (k--)
{
nums1[k] = arr[k];
}
// 释放动态开辟的内存空间
free(arr);
arr = NULL;
}
int main()
{
int i;
int arr1[1000] = { 1,4,6 };
int len1 = sizeof(arr1) / sizeof(arr1[0]);
int arr2[] = { 2,3,7 };
int len2 = sizeof(arr2) / sizeof(arr2[0]);
int m = 3;
// 测试第一个数组的元素有三个
//merge(arr1, len1, m, arr2, len2, len2);
//for (i = 0; i < m + len2; i++) { printf("%d ", arr1[i]); }
//printf("\n");
// 测试第一个数组的元素有两个
m = 2;
merge(arr1, len1, m, arr2, len2, len2);
for (i = 0; i < m+ len2; i++) { printf("%d ", arr1[i]); }
printf("\n");
}
```
