力扣刷题——4.寻找两个正序数组的中位数

题目要求在两个有序数组中找到中位数。由于时间复杂度要求为 O(log(m+n))，因此不能简单地将两个数组合并后再找中位数，而是需要用二分查找的思路来解决。

解决思路：二分查找 将问题转化为在两个有序数组中寻找第 k小的数，其中 k 是中位数的位置。

具体步骤： 1. 如果两个数组的总长度是偶数，则中位数是第 k小和第 k+1小的数的平均值。 2. 如果总长度是奇数，则中位数是第 k_小的数。 3. 通过二分查找，每次排除一半的元素，逐步缩小查找范围。

代码实现 #include <algorithm> #include <climits>

class Solution { public:     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {         int m = nums1.size();         int n = nums2.size();         int total = m + n;

        if (total % 2 == 1) {             // 总长度为奇数，返回第 k 小的数             return findKthElement(nums1, nums2, total / 2 + 1);         } else {             // 总长度为偶数，返回第 k 小和第 k+1 小的数的平均值             double left = findKthElement(nums1, nums2, total / 2);             double right = findKthElement(nums1, nums2, total / 2 + 1);             return (left + right) / 2.0;         }     }

private:     // 寻找第 k 小的元素     int findKthElement(vector<int>& nums1, vector<int>& nums2, int k) {         int m = nums1.size();         int n = nums2.size();         int index1 = 0, index2 = 0;

        while (true) {             // 边界情况             if (index1 == m) {                 return nums2[index2 + k - 1];             }             if (index2 == n) {                 return nums1[index1 + k - 1];             }             if (k == 1) {                 return min(nums1[index1], nums2[index2]);             }

            // 正常情况             int newIndex1 = min(index1 + k / 2 - 1, m - 1);             int newIndex2 = min(index2 + k / 2 - 1, n - 1);             int pivot1 = nums1[newIndex1];             int pivot2 = nums2[newIndex2];

            if (pivot1 <= pivot2) {                 k -= (newIndex1 - index1 + 1);                 index1 = newIndex1 + 1;             } else {                 k -= (newIndex2 - index2 + 1);                 index2 = newIndex2 + 1;             }         }     } };  

 复杂度分析 1. 时间复杂度：_O(log(m+n))_，每次排除一半的元素。 2. 空间复杂度：_O(1)_，只使用了常数级别的额外空间。

 边界情况 1. 一个数组为空：直接返回另一个数组的中位数。 2. 两个数组长度相等：需要处理偶数长度的中位数计算。 3. 所有元素都在一个数组中：需要确保不会越界。

总结 通过二分查找，可以在 O(log(m+n)) 的时间内找到两个有序数组的中位数。关键在于将问题转化为寻找第 k小的元素，并通过排除一半的元素逐步缩小查找范围。