欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode算法系列:4、Median of Two Sorted Arrays

程序员文章站 2022-07-15 10:53:26
...

目录

 

题目描述:

算法描述:

证明时间复杂度

从而得到算法复杂度为O(lg(m+n))算法实现:


题目描述:

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)).

You may assume nums1 and nums2 cannot be both empty.

 

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

算法描述:

我们能够想到的一般算法为定义两个指针,分别指向两个数组的头,然后比较指针指向数据的大小。根据结果,向后移动指针,直至找到中位数,但是这种算法的时间复杂度为O(m+n),明显不合要求。

要想将时间复杂度从O(m+n)提升为O(lg(m+n)),我们很容易想到分冶法,同时我们要能够将求中位数的问题等价为求两个数组的从小到大第k个数(num[k])的问题。

LeetCode算法系列:4、Median of Two Sorted Arrays

如上图,取数组1的第p个数,取数组2的第q个数(p+q = k),我们比较nums1[p]和nums2[q],根据结果,我们可以将问题简化

1 Nums1[p]=Nums2[q] 这两个数都可以认为是当前两个数组的第k个数
2 Nums1[p]>Nums2[q]

Nums1[p] >num[k] > Nums2[q]:

即我们所要找的数在数组A1和B2中,排列在第k-q位

3 Nums1[p]<Nums2[q]

Nums1[p] <num[k] <Nums2[q]:

即我们所要找的数在数组A2和B1中,排列在第k-p位

到这样,问题的关键就变成了如何取p(q可根据p和k求得)

在我的程序中我是通过两个数组的长度对k进行比例分配,同时考虑到p和q均在两数组的检索范围内。

证明时间复杂度

假设当前两个数组的长度分别为m和n,出现表中情况1的概率近似为0,出现表中2和3的概率近似为0.5,则下一次处理的数组长度的期望为:

LeetCode算法系列:4、Median of Two Sorted Arrays

于是可以认为:T(m+n)=T((m+n)/2)+O(1);

从而得到算法复杂度为O(lg(m+n))
算法实现:

//预计使用分冶法进行操作
//如果n+m等于偶数,我们要找到第(m+n)/2和(m+n)/2+1小的数
//如果n+m等于奇数,我们要找到第[(m+n)/2]+1小的数
class Solution {
public:
    double findkth(vector<int>& nums1, vector<int>& nums2,int start1,int l1,int start2,int l2,int k)
    {
        //用以观察每次递归时的参数变化
        std::cout << start1 << l1 << start2 << l2 << k << endl;
        //不同情况下的递归走向
        //递归的出口
        //k在两个数列中的划分,平分?比例划分?
        if(l1 == 0) return nums2[start2 + k - 1];
        else if(l2 == 0) return nums1[start1 + k -1];
        else if(k == 1) return min(nums1[start1] , nums2[start2]);
        else if(k == l1 + l2) return max(nums1[start1 + l1 - 1] , nums2[start2 + l2 - 1]);
        else
        {
            int p, q;
            //下面给f赋值运算如果没有强制转换为,会将l1/(l1+l2)的计算结果同步为l1和l2的数据类型,即强制转换为int型,之后赋值给f时再强制转换为double型,这样就会导致错误
            double f = double(l1)/double(l1 + l2);
            //如此分配是为了保证给p赋值的范围在(1,l1)之间
            p = min(max(int(f*k) , 1),l1);
            q = k - p;
            int suanz1 = nums1[start1 + p - 1];
            int suanz2 = nums2[start2 + q - 1];
            if(suanz1 == suanz2) return suanz1;
            else if(suanz1 > suanz2) return findkth(nums1, nums2, start1, p, start2 + q, l2 - q, p);
            else if(suanz2 > suanz1) return findkth(nums1, nums2, start1 + p, l1 - p, start2, q, q);
        }        
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if((n+m)%2 == 1) return findkth(nums1,nums2,0,m,0,n,(n+m+1)/2);
        else  return (findkth(nums1,nums2,0,m,0,n,(n+m)/2) + findkth(nums1,nums2,0,m,0,n,(n+m)/2 + 1))/2;
    }
};

 

相关标签: LeetCode