leetcode4. Median of Two Sorted Arrays

最新推荐文章于 2023-06-12 16:30:30 发布

Coding_Reading

最新推荐文章于 2023-06-12 16:30:30 发布

阅读量302

点赞数

分类专栏： LeetCode 数组

本文链接：https://blog.csdn.net/ProgrammeringLearner/article/details/61204032

版权

LeetCode 同时被 2 个专栏收录

32 篇文章

订阅专栏

数组

12 篇文章

订阅专栏

本文介绍了一种高效算法来找到两个已排序数组的中位数，通过递归比较两个数组中的元素，实现O(log(m+n))的时间复杂度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

hard程度题

题目:

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

两个升序的数组，求它们所有元素的中位数，要求复杂度为O（log （m+n））

。。。。。。完全不会，只会一个一个的递进比较大小，最坏情况下复杂度O(m+n)

参考的网上的解法

题目的一般形式为两个升序排列的数组，找出他们中第K大的元素

思路，类似于二分

假设nums1和muns2中的元素个数都大于K/2，将nums1和nums2中的第K/2个元素比较大小

则有三种情况

1.nums1[K / 2 - 1] > nums2[K / 2 - 1]

2.nums1[K / 2 - 1] = nums2[K / 2 - 1]

3.nums1[K / 2 - 1] < nums2[K / 2 - 1]

第一种情况,我们可以确定nums2中的前K/2个元素一定比我们要找的第K大的数小，可以除去

第二种情况,那么nums1和nums2中的第K/2个元素就是我们要找的第K大元素

第三种情况,我们可以确定nums1中的前K/2个元素一定比我们要找的第K大的数小，可以除去

因此我们可以写一个递归函数，终止条件

1.nums1或nums2为空，则返回nums1[K - 1]或nums2[K - 1]

2.K = 1时，返回返回min(nums1[1],nums2[1])

3.nums1[K / 2 - 1] = nums2[K / 2 - 1]返回两者中一个

AC解

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        int m = nums1.size();
        int n = nums2.size();
        int total = m + n;
        if (total & 0x1)    //奇数
            return findKth(nums1.begin(),m,nums2.begin(),n,total / 2 + 1);
        else
            return (findKth(nums1.begin(),m,nums2.begin(),n,total / 2) + 
                    findKth(nums1.begin(),m,nums2.begin(),n,total / 2 + 1)) / 2.0;
    }
    
    int findKth(std::vector<int>::const_iterator it_nums1,int m ,std::vector<int>::const_iterator
              it_nums2,int n ,int K)
    {
        if (m > n)  return findKth(it_nums2,n,it_nums1,m,K);//始终使前面一个容器元素个数少
        if (m == 0) return *(it_nums2 + K - 1);
        if (K == 1) return min(*it_nums1,*it_nums2);
        
        int i = min(m ,K / 2),j = K - i;
        if (*(it_nums1 + i - 1) > *(it_nums2 + j - 1))
            return findKth(it_nums1,m,it_nums2 + j,n - j,K - j);
        else if (*(it_nums1 + i - 1) < *(it_nums2 + j - 1))
            return findKth(it_nums1 + i,m - i,it_nums2,n,K - i);
        else 
            return *(it_nums1 + i - 1);
    }
};