【面试题】【C语言】寻找两个正序数组的中位数
寻找两个正序数组的中位数
仅供学习
题目
算法时间复杂度
二分查找算法，时间复杂度为 O(log(min(m, n)))，其中 m 和 n 分别是两个数组的长度。
子函数
查找两个数字的最大值
int max(int a, int b) {return a > b ? a : b;
}
查找两个数字的最小值
int min(int a, int b) {return a < b ? a : b;
}
findMedianSortedArrays
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {// Ensure nums1 is the smaller arrayif (nums1Size > nums2Size) {return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);}int x = nums1Size;int y = nums2Size;int low = 0;int high = x;while (low <= high) {int partitionX = (low + high) / 2;int partitionY = (x + y + 1) / 2 - partitionX;int maxX = (partitionX == 0) ? INT_MIN : nums1[partitionX - 1];int minX = (partitionX == x) ? INT_MAX : nums1[partitionX];int maxY = (partitionY == 0) ? INT_MIN : nums2[partitionY - 1];int minY = (partitionY == y) ? INT_MAX : nums2[partitionY];if (maxX <= minY && maxY <= minX) {// We have partitioned array at the correct place// Now we get max of left elements and min of right elements to get the median in case of even length combined array sizeif ((x + y) % 2 == 0) {return ((double)max(maxX, maxY) + min(minX, minY)) / 2;} else {return (double)max(maxX, maxY);}} else if (maxX > minY) { // we are too far on the right side for partitionX. Go on left side.high = partitionX - 1;} else { // we are too far on the left side for partitionX. Go on right side.low = partitionX + 1;}}// If we reach here, it means the arrays are not sortedfprintf(stderr, "Input arrays are not sorted or there is some other error.\n");return -1;
}
说明
- 该代码实现了一个查找两个正序数组中位数的算法，使用了二分查找法来优化时间复杂度。
- findMedianSortedArrays 函数首先确保第一个数组（nums1）是较小的一个，这样可以减小搜索范围。
- 在 while 循环中，通过二分查找确定两个数组的分割点，使得分割后的左半部分和右半部分元素数量接近。
- 根据分割点计算最大左边元素和最小右边元素，进而确定中位数。
- 主函数通过示例数据验证了算法的正确性。