Leetcode笔记目录

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

• Leetcode笔记目录
• 一、题目描述
• 二、解题过程
• • 1.思想
  • 2.代码
• 三、总结

hard)

一、题目描述

给定两个大小为 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。

二、解题过程

1.思想

n+m的复杂度解法比较容易，要想log(n+m)就要使用二分法，对于该题是很复杂的，推荐解法可以视作套用左闭右开模板，比较优雅易懂：

• 注意：为什么二分法中只需要判断一个条件就可以了，没太搞懂，作者解答：二分法是寻找到第一个满足条件的值，即最小的nums1[i]，即i最小，可见若数组中有解的话，那么此时的i对于nums[i-1]<=nums[j]定是满足的；

2.代码

int max(int a,int b){
        if(a>b)return a;
        else return b;
    }
    int min(int a,int b){
        if(a>b)return b;
        else return a;
    }
    int result(vector<int>& nums1, vector<int>& nums2, int k){
        int left = max(0,k-nums2.size()), right = min(k,nums1.size()),mid;
        while(left<right){
            mid = left + (right-left)/2;
            if(nums1[mid]>=nums2[k-mid-1]) right=mid;
            else left=mid+1;
        }
        int leftnums1 = left == 0?-100001:nums1[left-1];
        int leftnums2 = left == k?-100001:nums2[k-left-1];
        return max(leftnums1,leftnums2);
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int k=(nums1.size()+nums2.size());
        if(k%2==1) return result(nums1,nums2,k/2+1)*1.00000;
        else return (result(nums1,nums2,k/2)+result(nums1,nums2,k/2+1))/2.00000;
    }
           

• 注意
  • 边界判断：若i为0，则此时就是nums2数组中的第k个元素，若i为k，则此时就是nums1数组中的第k个元素。

三、总结

该题实为求两有序数组的第k小的值，该解法算是使用左闭右开，比较合适。