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

题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

思路

分治思想
n : num1.length + num2.length
若 n 为奇数 , 中位数为合并后数组下标 n / 2 的值
若 n 为偶数 , 中位数为合并后数组下标（ n/2 + n/2+1 ） / 2 的值
设 left , right 变量代表 n/2 n/2+1的值
只需要求出 left , right 即可
设 a ,b 两个指针分别指向 nums1 和 num2 的 0 下标
遍历 n/2 +1 次，若 nums1[a] < nums2[b] , right的值赋给 left , right = nums1[a] , a++ , 大于则相反
此时遍历到最后 right == n/2 + 1 ,left = n/2
即可得到 中位数

代码

public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
    
        int len = nums1.length + nums2.length;
        int aStart=0 , bStart=0;
        int left=-1,right=-1;
        for(int i = 0;i <= len/2; i++){
    
            left = right;
            if(  aStart < nums1.length && (   bStart >= nums2.length  || nums1[aStart] < nums2[bStart] )){
    
                right = nums1[aStart++];
            }else{
    
                right = nums2[bStart++];
            }
        }
        if( len % 2 == 0){
    
            return (left + right) / 2.0;
        }else{
    
            return right;
        }
    }