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

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

力扣题目链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/

题意 给定两个大小分别为 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

解题思路 由于两个数组都是有序的，因此只要从头开始比较直到找到中位数结束。 如果两数组长度为奇数则中位数只有一个，偶数则有两个求平均即可。

Java代码

class Solution {
          
   
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
          
   
        int n = nums1.length;
        int m = nums2.length;
        double sum = 0.0;
        //i指向nums1数组，j指向nums2数组
        for(int i=0,j=0;;){
          
   
            //记录较小的值
            int temp = 0;
            //若指针越界则说明一个数组遍历完
            if(i >= n){
          
   
                temp=nums2[j++];
            }else if(j >= m){
          
   
                temp=nums1[i++];
            }
            else if(nums1[i]>nums2[j]){
          
    //比较nums1[i]和nums2[j]遍历较小的值
                temp=nums2[j++];
            }else if(nums1[i]<=nums2[j]){
          
   
                temp=nums1[i++];
            }
            //若为中位数则加在sum中，总长度为奇数则加一次，偶数加两次
            if((i+j) >= (n+m+1)/2){
          
   
                sum+=temp;
            }
            //遍历完中位数则退出循环
            if((i+j) >= (n+m+2)/2){
          
   
                break;
            }
        }
        if(((n+m) & 1) ==0){
          
   
            return sum/2;
        }else{
          
   
            return sum;
        }
    }
}