LeetCode 4. Median of Two Sorted Arrays题目解析-wowAC

Description

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

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

The median is 2.0

Example 2:

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

The median is (2 + 3)/2 = 2.5

题目复述

给定两个升序的数组nums1, nums2,长度分别为m,n,找出这两个数组的中位数。程序运行的时间复杂度应该为O(log(m+n))

中位数定义:数组元素个数为奇数个时取最中间的数,偶数个数时取最中间的两个数的平均数。

题目解析

由于题目要求时间复杂度为O(log(m+n)),因此考虑使用分治法,首先我们可以将问题转化为求解第k小,假设我们将数组nums1[l1 – r1]和数组nums2[l2 – r2]分解成nums1[l1 – mid1], nums1[mid1+1 – r1]和nums2[l2 – mid2],nums2[mid2+1, r2],其中mid1-l1+1+mid2-l2+1 == k, 那么我们可以得出以下结论,如果nums1[mid1] < nums2[mid2],那么第k小的数肯定不在nums1[l1 – mid1]nums2[mid2+1 – r2]中,反之亦然。这样每次就可以去头掐尾,直到递归终止条件。下面给出证明,假设第k小的数在nums1[l1 – mid1]中,那么对于任意的nums1[l1 – mid1]中的数a,小于等于a的个数应该大于等于k,然而根据已知条件得出这是不可能的。递归终止的条件为其中一个数组为空或者k=1(不能再分)。在实现的时候为了方便我们可以规定nums1中的有效个数恒小于等于nums2,还需注意的是在求解第k小的时候可能nums1的有效元素个数小于k/2,这时候我们只需要取min(nums1.size(), k/2),但是必须保证mid1-l1+1+mid2-l2+1 == k。

class Solution {
public:
    int get_Kth(vector<int>& nums1, int l1, int r1, vector<int>& nums2, int l2, int r2, int k) {
        if(r1-l1+1 > r2-l2+1) //nums1个数恒小于等于nums2
            return get_Kth(nums2, l2, r2, nums1, l1, r1, k);
        
        if(l1 > r1) //nums1空
            return nums2[l2 + k - 1];
        if(k == 1)  //k = 1
            return min(nums1[l1], nums2[l2]);
        
        int nums1_lnum = min(k/2, r1-l1+1);
        int nums2_lnum = k - nums1_lnum;   //mid1-l1+1+mid2-l2+1 == k
        int mid1 = l1 + nums1_lnum - 1;
        int mid2 = l2 + nums2_lnum - 1;
        
        if(nums1[mid1] < nums2[mid2])     //去头掐尾之后需要修正k
            return get_Kth(nums1, mid1+1, r1, nums2, l2, mid2, k-(mid1-l1+1));
        else 
            return get_Kth(nums1, l1, mid1, nums2, mid2+1, r2, k-(mid2-l2+1));
    }
    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        double res = 0.0;
        int total = nums1.size() + nums2.size();
        if(total%2 == 1) {
            res = get_Kth(nums1, 0, nums1.size()-1, nums2, 0, nums2.size()-1, total/2+1);
        }else {
            res += get_Kth(nums1, 0, nums1.size()-1, nums2, 0, nums2.size()-1, total/2);
            res += get_Kth(nums1, 0, nums1.size()-1, nums2, 0, nums2.size()-1, total/2+1);
            res /= 2.0;
        }
        return res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注