合并有序数组
- 题目描述:
- 解法思路:
- 解法代码:
- 运行结果:
题目描述:
输入两个升序排列行的序列,将两个序列合并为一个有序序列并输出。
输入包含三行,第一包含两个正整数n, m,用空格分隔。n表示第二行第⼀个升序序列中数字的个数,m表示第三行第二个升序序列中数字的个数。其中1<=n<=30, 1<=m<=30 第二⾏包含 n 个整数,用空格分隔。第三行包含 m 个整数,用空格分隔。输出为一行,输出长度为n+m的升序序列,即长度为n的升序序列和长度为m的升序序列中的元素重新进行升序序列排列合并。
测试:
输⼊:
5 6
1 3 7 9 22
2 8 10 17 33 44
输出:
1 2 3 7 8 9 10 17 22 33 44
解法思路:
定义⼀个长度为 n+m 的新数组 arr3 ,将两个有序数组合并到 arr3 数组中,使得 arr3 数组有序。
1. 定义⼀个长度为 n+m 的新数组 arr3 ,以及两个指针 i 和 j ,分别指向 arr1 和arr2 的开头;
2. 定义⼀个计数器 k ,初始化为 0;
3. 比较 arr1[i] 和 arr2[j] ,将较小的数存入 arr3 中,并将对应指针向后移动一位;
4. 将计数器 k 加 1;
5. 重复步骤 3 和 4 直到某个指针越界;
6. 加粗样式将另一个指针指向的数组的剩余所有元素依次存入 arr3 中,存入同时将计数器 k 的值自增1;
7. 至此, arr3 数组中的元素为 arr1 数组和 arr2 数组合并并排序后的结果,按序输出前 k个元素即可。
解法代码:
#include <stdio.h>
int main() {
int n = 0;
int m = 0;
//输⼊
scanf("%d %d", &n, &m);
//⽀持变⻓数组的
int arr1[30] = {0};
int arr2[30] = {0};
int arr3[60] = {0};
//输⼊arr1
int i = 0;
for (i = 0; i < n; i++)
{
scanf("%d", &arr1[i]);
}
//输⼊arr2
for (i = 0; i < m; i++)
{
scanf("%d", &arr2[i]);
}
//合并arr1和arr2到arr3数组中
i = 0; //i遍历arr1
int j = 0;//j遍历arr2
int k = 0;//k遍历arr3
//合并两个数组的元素⾄arr3数组中
while (i < n && j < m)
{
//⽐较两个指针指向的元素⼤⼩
//arr1数组当前元素较⼩,将此值放⼊arr3数组并令i和k后移
if (arr1[i] < arr2[j])
{
arr3[k] = arr1[i];
i++;
k++;
}
//arr2数组当前元素较⼩,将此值放⼊arr3数组并令j和k后移
else
{
arr3[k] = arr2[j];
j++;
k++;
}
}
//若指针i越界,则arr1数组所有元素已经放⼊arr3数组
//arr2数组中有剩余元素,将它们依次放⼊arr3数组
if (i == n)
{
for (; j < m; j++)
{
arr3[k] = arr2[j];
k++;
}
}
//若指针j越界,则arr2数组所有元素已经放⼊arr3数组
//arr1数组中有剩余元素,将它们依次放⼊arr3数组
if (j == m)
{
for (; i < n; i++)
{
arr3[k] = arr1[i];
k++;
}
}
//打印
for (k = 0; k < m + n; k++)
{
printf("%d ", arr3[k]);
}
return 0;
}