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

布满荆棘的人生 2024-03-26 15:21 45阅读 0赞

![在这里插入图片描述][e255e005e2114980932f89a0611cdaf1.png]  
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = \[1,3\], nums2 = \[2\]  
输出：2.00000  
解释：合并数组 = \[1,2,3\] ，中位数 2  
示例 2：

输入：nums1 = \[1,2\], nums2 = \[3,4\]  
输出：2.50000  
解释：合并数组 = \[1,2,3,4\] ，中位数 (2 + 3) / 2 = 2.5

提示：

nums1.length == m  
nums2.length == n  
0 <= m <= 1000  
0 <= n <= 1000  
1 <= m + n <= 2000  
\-106 <= nums1\[i\], nums2\[i\] <= 106

class Solution \{  
public double findMedianSortedArrays(int\[\] nums1, int\[\] nums2) \{  
int n1 = nums1.length;  
int n2 = nums2.length;

if (n1 > n2) return findMedianSortedArrays(nums2, nums1);
    
        int iMin = 0;
        int iMax = n1;
        int mid = (n1 + n2 + 1) / 2;
        double median;
    
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = mid - i; 
            if (i < iMax && nums2[j - 1] > nums1[i]) {
                iMin++;
            }
            else if (i > iMin && nums1[i - 1] > nums2[j]) {
                iMax--; 
            }
            else {
                int maxLeft; 
                if (i == 0) 
                    maxLeft = nums2[j - 1];
                else if (j == 0) 
                    maxLeft = nums1[i - 1];
                else 
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                
                if ((n1 + n2) % 2 == 1) {
                    return maxLeft;
                }
                
                int minRight;
                if (i == n1)
                    minRight = nums2[j];
                else if (j == n2)
                    minRight = nums1[i];
                else
                    minRight = Math.min(nums1[i], nums2[j]);
                
                median = (double) (maxLeft + minRight) / 2.0;
                return median;
            }
        }
        return 0.0;
    }

[e255e005e2114980932f89a0611cdaf1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/1405c3a022104cc28b310b46481b8f6c.png