第四题：求两个有序数组的中位数（Median of Two Sorted Arrays）

本文主要是介绍第四题：求两个有序数组的中位数（Median of Two Sorted Arrays），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2，请你找出这两个有序数组的中位数。

示例：

1. 输入：nums1 = [1, 3], nums2 = [2]
   输出：2.0

2. 输入：nums1 = [1, 2], nums2 = [3, 4]
   输出：2.5

要求： 你必须在对数时间复杂度 O(log(min(m, n))) 内解决这个问题。

解题思路

1. 二分查找方法（最优解法）

   这个问题的核心是利用二分查找算法在两个有序数组中找到中位数。我们可以将问题转化为在两个数组中寻找一个分割点，使得左侧的元素总是小于右侧的元素，并且左侧的元素数量与右侧的元素数量尽可能相等。

   具体步骤如下：

   1. 确保 nums1 的长度小于等于 nums2，如果不是，则交换它们。

   2. 对于较短的数组 nums1，使用二分查找来确定分割点。分割点将数组 nums1 划分为 left1 和 right1，同时在 nums2 中确定对应的分割点 left2 和 right2。

   3. 根据当前的分割点计算 left1, right1, left2, right2，然后调整分割点以满足以下条件：

      • left1 和 left2 的最大值要小于等于 right1 和 right2 的最小值。

   4. 如果分割点满足条件，则根据总元素个数的奇偶性计算中位数。

   5. 如果分割点不满足条件，则根据条件调整分割点，继续二分查找。

C 语言实现

#include <stdio.h>
#include <limits.h>double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {if (nums1Size > nums2Size) {int* tempArr = nums1;nums1 = nums2;nums2 = tempArr;int tempSize = nums1Size;nums1Size = nums2Size;nums2Size = tempSize;}int imin = 0, imax = nums1Size, half_len = (nums1Size + nums2Size + 1) / 2;while (imin <= imax) {int i = (imin + imax) / 2;int j = half_len - i;if (i < nums1Size && nums2[j - 1] > nums1[i]) {imin = i + 1;} else if (i > 0 && nums1[i - 1] > nums2[j]) {imax = i - 1;} else {int max_of_left, min_of_right;if (i == 0) max_of_left = nums2[j - 1];else if (j == 0) max_of_left = nums1[i - 1];else max_of_left = (nums1[i - 1] > nums2[j - 1]) ? nums1[i - 1] : nums2[j - 1];if ((nums1Size + nums2Size) % 2 == 1) return max_of_left;if (i == nums1Size) min_of_right = nums2[j];else if (j == nums2Size) min_of_right = nums1[i];else min_of_right = (nums1[i] < nums2[j]) ? nums1[i] : nums2[j];return (max_of_left + min_of_right) / 2.0;}}return 0.0;
}

Java 实现

public class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {if (nums1.length > nums2.length) {int[] temp = nums1;nums1 = nums2;nums2 = temp;}int x = nums1.length;int y = nums2.length;int low = 0, high = x;while (low <= high) {int partitionX = (low + high) / 2;int partitionY = (x + y + 1) / 2 - partitionX;int maxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];int minX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];int maxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];int minY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];if (maxX <= minY && maxY <= minX) {if ((x + y) % 2 == 0) {return (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2.0;} else {return Math.max(maxX, maxY);}} else if (maxX > minY) {high = partitionX - 1;} else {low = partitionX + 1;}}throw new IllegalArgumentException("Input arrays are not sorted.");}
}

Python 实现

def findMedianSortedArrays(nums1, nums2):if len(nums1) > len(nums2):nums1, nums2 = nums2, nums1x, y = len(nums1), len(nums2)low, high = 0, xwhile low <= high:partitionX = (low + high) // 2partitionY = (x + y + 1) // 2 - partitionXmaxX = float('-inf') if partitionX == 0 else nums1[partitionX - 1]minX = float('inf') if partitionX == x else nums1[partitionX]maxY = float('-inf') if partitionY == 0 else nums2[partitionY - 1]minY = float('inf') if partitionY == y else nums2[partitionY]if maxX <= minY and maxY <= minX:if (x + y) % 2 == 0:return (max(maxX, maxY) + min(minX, minY)) / 2.0else:return max(maxX, maxY)elif maxX > minY:high = partitionX - 1else:low = partitionX + 1raise ValueError("Input arrays are not sorted.")

时间复杂度

所有三种实现的方法的时间复杂度都是 (O(\log(\min(m, n))))，其中 (m) 和 (n) 分别是两个数组的长度。这是因为我们主要是在较短的数组上进行二分查找。

这篇关于第四题：求两个有序数组的中位数（Median of Two Sorted Arrays）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---