4. 寻找两个正序数组的中位数

我会带着你远行 2022-10-10 12:56 153阅读 0赞

> 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
> 
> 示例 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  
> 示例 3：
> 
> 输入：nums1 = \[0,0\], nums2 = \[0,0\]  
> 输出：0.00000

class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
                /***
                
                1首先分割两个数组  分割线左边的元素个数之和= (总个数+1)/2  前提:保证nums1长度<nums2的长度
                2找到分割线返回结果:   (注意越界问题  比如第一个数组或者第二个数组分割线在第一个元素,或者最后一个元素)
                    如果是奇数: 返回分割线左边两个元素里面的最大值
                    如果是偶数: 返回分割线(左边的那个最大值+右边的那个最大值)/2
                 */
    
            if(nums1.length>nums2.length){
                return findMedianSortedArrays(nums2,nums1);
            }
            int totalLeft=(nums1.length+nums2.length+1)/2;
            int  left=0;
            int right=nums1.length;
            while(left<right){
                int i=left+right+1>>1;//第一个数组里面分割线右边第一个元素下标
                int  j=totalLeft-i;//第二个数组里面分割线右边第一个元素下标
                if(nums1[i-1]>nums2[j]){//第一个数组分割线左边第一个元素>第二个数组里面分割线右边第一个元素 不满足条件 分割线左移
                    right=i-1;
                }else{
                    left=i;
                }
            }
            //退出找到了第一个分组里面分割线右边第一个元素下标left 
            int i=left;
            int  j=totalLeft-left;//第二个分组里面分割线右边第一个元素下标
            /**
            if两个数组之和为奇数: 返回分割线左边的那个最大值即可
            if两个数组之和为偶数:   返回分割线(左边的那个最大值+右边的那个最大值)/2
             */
             //但是有可能越界
             int leftMax1=(i==0?Integer.MIN_VALUE:nums1[i-1]);//第一个数组里面分割线左边最大值
             int leftMax2=(j==0?Integer.MIN_VALUE:nums2[j-1]);//第二个数组里面分割线左边最大值
             int rightMin1=(i==nums1.length?Integer.MAX_VALUE:nums1[i]);//第一个数组里面分割线右边最小值
             int rightMin2=(j==nums2.length?Integer.MAX_VALUE:nums2[j]);//第二个数组里面分割线右边最小值
             if((nums1.length+nums2.length)%2==1){
                 //说明是奇数  返回分割线左边的那个最大值即可
                 return Math.max(leftMax1,leftMax2);
             }else{
                 //注意一定/2.0否则他给 取整了  因为math.max .min返回的是整形
                 return ((Math.max(leftMax1,leftMax2)+Math.min(rightMin1,rightMin2))/2.0);
             }
             
        }
    }