[0004] 寻找两个有序数组的中位数.md

title	tags	categories	author	comments	updated	permalink	mathjax	top	description	date
[0004] 寻找两个有序数组的中位数	leetcode	leetcode	张学志	true	false		false	false	...	2019-12-31 16:00:04 -0800

题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

Related Topics

数组

二分查找

分治算法

题目代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

    }
};

题目解析

方法一

• 割

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if(m < n)
            return findMedianSortedArrays(nums2, nums1);
        if(n==0)
            return ((double)nums1[(m-1)/2] + (double)nums1[m/2]) / 2.0;
        int left = 0;
        int right = n * 2;
        while(left <= right){
            int mid2 = (left + right) / 2;
            int mid1 = m + n - mid2;
            double L1 = mid1 == 0 ? INT_MIN : nums1[(mid1-1)/2];
            double L2 = mid2 == 0 ? INT_MIN : nums2[(mid2-1)/2];
            double R1 = mid1 == m * 2 ? INT_MAX : nums1[mid1/2];
            double R2 = mid2 == n * 2 ? INT_MAX : nums2[mid2/2];
            if(L1 > R2)
                left = mid2 + 1;
            else if(L2 > R1)
                right = mid2 - 1;
            else
                return (max(L1, L2) + min(R1, R2)) / 2;
        }
        return -1;
    }
};

方法二

• 递归法
• 参考：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu-b/

#include <vector>
using namespace std;

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if(m>n) // ensure m<=n
            return findMedianSortedArrays(nums2, nums1);
        int iMin = 0;
        int iMax = m;
        int halfLen = (m+n+1)/2;
        while(iMin<=iMax){
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if(i<iMax && nums2[j-1]>nums1[i])
                iMin = i+1;
            else if(i>iMin && nums1[i-1]>nums2[j])
                iMax = i-1;
            else{
                int maxLeft = 0;
                if(i==0)
                    maxLeft = nums2[j-1];
                else if(j==0)
                    maxLeft = nums1[i-1];
                else
                    maxLeft = max(nums1[i-1], nums2[j-1]);
                if((m+n)%2==1)
                    return maxLeft;

                int minRight = 0;
                if(i==m)
                    minRight = nums2[j];
                else if(j==n)
                    minRight = nums1[i];
                else
                    minRight = min(nums2[j], nums1[i]);

                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
};

方法三