解决寻找两个正序数组中位数问题：C语言实现与解析

在算法学习和实际编程应用中，处理数组相关的问题是很常见的。其中，寻找两个正序数组的中位数就是一个经典的题目，不仅考验对数组操作的熟悉程度，还涉及到对算法效率的考量。今天，我们就来深入探讨如何使用C语言解决这一问题。

一、题目描述

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2 ，要求找出并返回这两个正序数组的中位数。并且，算法的时间复杂度应该为 O(log (m + n)) 。例如：

- 输入：nums1 = [1,3] ， nums2 = [2] ，输出： 2.000000 ，因为合并数组 = [1,2,3] ，中位数是 2 。

- 输入： nums1 = [1,2] ， nums2 = [3,4] ，输出： 2.500000 ，因为合并数组 = [1,2,3,4] ，中位数是 (2 + 3) / 2 = 2.5 。

二、解题思路

要解决这个问题，最直接的方法是先将两个数组合并成一个新的有序数组，然后根据新数组的长度是奇数还是偶数来计算中位数。具体步骤如下：

计算合并后数组的大小：

将两个数组的长度相加，得到合并后数组的总长度 n 。

分配内存并合并数组：

使用 malloc 函数动态分配一块足够大的内存空间来存储合并后的数组。然后，通过 memcpy 函数将 nums1 和 nums2 的元素依次复制到新数组中。

对合并后的数组进行排序：

调用C标准库中的 qsort 函数对合并后的数组进行排序。 qsort 函数需要一个比较函数，这里我们定义了 cmp_int 函数来指定整数的比较规则。

计算中位数：

根据合并后数组的长度 n 的奇偶性来计算中位数。如果 n 是偶数，中位数是中间两个元素的平均值；如果 n 是奇数，中位数就是中间的那个元素。

释放内存：

使用完动态分配的内存后，通过 free 函数将其释放，以避免内存泄漏。

三、代码实现

c#include <stdio.h>#include <stdlib.h>#include <string.h>// 比较函数，用于qsort排序int cmp_int(const void*e1,const void*e2) {return *(int*)e1 - *(int*)e2;}// 寻找两个正序数组中位数的函数double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {// 计算合并后数组的大小int n = nums1Size + nums2Size;// 动态分配内存存储合并后的数组int *ps = (int*)malloc(sizeof(int) * (nums1Size + nums2Size));if (ps == NULL) {// 内存分配失败处理return 0.0; }// 将nums1的元素复制到新数组memcpy(ps, nums1, nums1Size * sizeof(int));// 将nums2的元素复制到新数组memcpy(ps + nums1Size, nums2, nums2Size * sizeof(int));// 对合并后的数组进行排序qsort(ps, n, sizeof(int), cmp_int);double temp;if (n % 2 == 0) {// 数组长度为偶数时计算中位数temp = (ps[n/2 - 1] + ps[n/2]) / 2.0;} else {// 数组长度为奇数时计算中位数temp = ps[n/2];}// 释放动态分配的内存free(ps);return temp;}

四、代码解析

比较函数 cmp_int ：

该函数是为 qsort 函数定制的比较规则。它接受两个指向 void 类型的指针 e1 和 e2 ，在函数内部将它们强制转换为指向 int 类型的指针，然后返回两个整数的差值。 qsort 函数会根据这个差值来决定元素的排序顺序。

主函数 findMedianSortedArrays ：

- 内存分配与检查：使用 malloc 分配内存给 ps 指针指向的数组。如果分配失败（ ps 为 NULL ），直接返回 0.0 ，并在实际应用中可以进一步添加错误提示信息。

- 数组合并：

通过两次 memcpy 函数调用，分别将 nums1 和 nums2 的内容复制到新数组 ps 中。

- 数组排序：

调用 qsort 函数，传入合并后的数组 ps 、数组长度 n 、每个元素的大小 sizeof(int) 以及比较函数 cmp_int ，完成排序操作。

- 中位数计算：

根据 n 的奇偶性，分别计算并存储中位数到 temp 变量中。

- 内存释放：

使用 free 函数释放之前动态分配的内存，确保程序不会出现内存泄漏问题。

五、时间复杂度分析

当前实现中，合并数组的操作时间复杂度为 O(m + n) ，排序操作使用了 qsort ，其平均时间复杂度为 O((m + n) log (m + n)) 。虽然这个实现满足了功能需求，但时间复杂度并没有达到题目要求的 O(log (m + n)) 。要达到题目要求的时间复杂度，可以使用二分查找的思路，通过划分两个数组的左右部分，利用中位数的性质来优化算法，不过这就需要更复杂的逻辑和代码实现。