pat模拟题—7-11 两个序列的中位数

一个长度为n(n⩾1)的升序序列S,处在第2n​个位置的数称为序列S的中位数(median number),例如，序列S1={10,13,14,16,18,19}的中位数是14。两个序列的中位数是它们所有元素的升序序列的中位数，例如，S2={2,4,8,9,20,21},则S1和S2的中位数是13。现有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列的中位数。

输入格式:

输入在三行进行，第一行1个非负整数N，表示两个数列的长度,第二行和第三行，每行N个非负整数，数与数之间用空格间隔。

输出格式:

在一行内输出一个整数。

输入样例:

6
8 11 14 15 17 19
2 4 6 9 10 12

输出样例:

10

方法一：探索使用二分搜索算法找到两个排序数组的中位数

在本篇博客中，我们将探讨一个使用二分搜索算法来找到两个排序数组的中位数的C程序。我们将在代码中提供详细的解释和注释，以帮助读者理解每一步的目的。

#include <stdio.h>int main()
{// 读取输入的整数nint n;scanf("%d", &n);// 定义两个长度为n的数组a和bint a[n], b[n];// 循环读取n个整数到数组a中for (int i = 0; i < n; i++){scanf("%d", &a[i]);}// 循环读取n个整数到数组b中for (int i = 0; i < n; i++){scanf("%d", &b[i]);}// 初始化四个指针l1, r1, l2, r2int l1 = 0, r1 = n - 1, l2 = 0, r2 = n - 1;// 使用二分搜索找到两个数组的中位数while (l1 < r1 || l2 < r2){int mid1 = (l1 + r1) >> 1;  // 计算数组a的中间位置int mid2 = (l2 + r2) >> 1;  // 计算数组b的中间位置// 如果两个中间位置的元素相等，那么这个元素就是中位数if (a[mid1] == b[mid2]){printf("%d", a[mid1]);return 0;}else if (a[mid1] < b[mid2])  // 如果a的中位数小于b的中位数{if ((l1 + r1) % 2 == 0) l1 = mid1;  // 更新a的左边界else l1 = mid1 + 1;  // 更新a的左边界r2 = mid2;  // 更新b的右边界}else  // 如果a的中位数大于b的中位数{if ((l2 + r2) % 2 == 0) l2 = mid2;  // 更新b的左边界else l2 = mid2 + 1;  // 更新b的左边界r1 = mid1;  // 更新a的右边界}}// 打印两个数组合并后的中位数printf("%d", a[l1] < b[l2] ? a[l1] : b[l2]);return 0;
}

上面的代码是用来找到两个有序数组a和b的中位数的算法。代码的运行逻辑如下：

        1. 首先从标准输入中读取整数n，表示数组a和b的长度。
        2. 然后定义了两个长度为n的数组a和b，分别用来存储输入的整数。
        3. 接着使用循环分别读取n个整数到数组a和数组b中。
        4. 初始化四个指针l1、r1、l2、r2，分别表示数组a和数组b的左右边界。
        5. 使用二分搜索的思想，通过不断缩小搜索范围，找到两个数组的中位数。
        6. 在循环中，首先计算数组a和数组b的中间位置mid1和mid2。
        7. 如果a[mid1]等于b[mid2]，则直接打印出中位数并结束程序。
        8. 否则，如果a[mid1]小于b[mid2]，则更新a的左边界和b的右边界，以缩小搜索范围。
        9. 如果a[mid1]大于b[mid2]，则更新b的左边界和a的右边界，以缩小搜索范围。
       10. 最后，打印出两个数组合并后的中位数，即a[l1]和b[l2]中的较小值。

        这样就完成了找到两个有序数组的中位数的过程。

方法二：使用快速排序算法找到排序数组的中位数

#include<stdio.h>
#include<stdlib.h>// cmp函数用于快速排序
int cmp(const void* a,const void* b)
{// 比较两个整数的大小return *(int*)b - *(int*)a;
}int main()
{int n;int a[1000001];// 从标准输入中读取一个整数nscanf("%d",&n);// 循环读取2n个整数到数组a中for(int i=0;i<n*2;i++){scanf("%d",&a[i]);}// 使用快速排序对数组a进行排序qsort(a,n*2,sizeof(a[0]),cmp);// 打印排序后的数组a的中位数printf("%d\n",a[n]);return 0;
}

上面的代码是用来找到两个有序数组a和b的中位数的快速排序算法。代码的运行逻辑如下：

        1. 首先从标准输入中读取整数n，表示数组a和b的长度。
        2. 然后定义了一个长度为2n的数组a，用来存储输入的2n个整数。
        3. 接着使用循环分别读取2n个整数到数组a中。
        4. 使用快速排序函数qsort对数组a进行排序，排序的方式是按照从大到小的顺序排列。
        5. 最后，打印出排序后的数组a的中位数，即a[n]。

qsort()函数是C语言标准库中提供的快速排序函数，其函数原型如下：

void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

qsort()函数的参数说明如下：

        1. base：指向要排序的数组的首元素的指针。
        2. nmemb：要排序的元素个数。
        3. size：每个元素的大小，以字节为单位。
        4. compar：比较函数，用于确定元素之间的相对顺序。该函数指针指向一个比较函数，该函数接受两个指向常量对象的指针，然后返回一个整数值，表示两个指针所指向的元素的相对顺序。

        快速排序是一种常见的排序算法，其基本思想是通过分治的方式，将一个大问题分解成若干个小问题，然后递归地解决这些小问题。快速排序的具体实现步骤如下：

        1. 首先选择一个基准元素，一般选择第一个或最后一个元素。
        2. 然后将待排序的元素分成两部分，一部分比基准元素小，一部分比基准元素大。
        3. 对这两部分元素分别进行递归排序。
        4. 最后将排序后的两部分元素合并起来。

快速排序的时间复杂度为O(nlogn)，其中n为待排序元素的个数。大家可以先看看，后期我会出一期快速排序函数的题集，当然得在我学习完之后。