宁夏建设注册中心网站,仿淘宝网站制作,wordpress安装2个网站,东莞开发方案公司一个长度为n(n⩾1)的升序序列S,处在第2n个位置的数称为序列S的中位数(median number),例如#xff0c;序列S1{10,13,14,16,18,19}的中位数是14。两个序列的中位数是它们所有元素的升序序列的中位数#xff0c;例如#xff0c;S2{2,4,8,9,20,21},则S1和S2的中位数是13。现有… 一个长度为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.hint 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]中的较小值。 这样就完成了找到两个有序数组的中位数的过程。 方法二使用快速排序算法找到排序数组的中位数 #includestdio.h
#includestdlib.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 i0;in*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为待排序元素的个数。大家可以先看看后期我会出一期快速排序函数的题集当然得在我学习完之后。
