Java怎么寻找两个有序数组的中位数

这篇文章主要介绍“Java怎么寻找两个有序数组的中位数”,在日常操作中,相信很多人在Java怎么寻找两个有序数组的中位数问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”Java怎么寻找两个有序数组的中位数”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

创新互联建站自2013年起,是专业互联网技术服务公司,拥有项目网站设计、成都网站设计网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元吴堡做网站,已为上家服务,为吴堡各地企业和个人服务,联系电话:18982081108

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

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

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

1.自己的想法是 一共m + n 个,我们可以新建一个List 然后每把最小的数放进去,代码如下:

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        leng = len(nums1) + len(nums2)
        tmpLen = leng//2 + 1
        newList = [0]*tmpLen
        i = 0
        j = 0
        for k in range(tmpLen):
            if i == len(nums1):
                newList[k] = nums2[j]
                j += 1
            elif j == len(nums2):
                newList[k] = nums1[i]
                i += 1
            else:
                if nums1[i] < nums2[j]:
                    newList[k] = nums1[i]
                    i += 1
                else:
                    newList[k] = nums2[j]
                    j += 1
        if leng %2 == 0:
            return (newList[tmpLen - 2] + newList[tmpLen - 1])/2
        else:
            return newList[tmpLen - 1]

2.类似与折半查找的思路,

由于题目要求的时间复杂度是(log(m+n)),如果我们直接把两个数组整合一起,那么时间复杂度肯定超过(log(m+n))。所以整理肯定是不行的。那么还有什么方法吗?答案是肯定的。

     首先我们要先了解中位数的概念,中位数就是有序数组的中间那个数。那么如果我们将比中位数小的数和比中位数大的数去掉同样的个数,中位数的值也不会变化(数组的个数为偶数的时候另外讨论,因为那时候中位数是中间两个数的平均值,所以中位数旁边两个数不能去掉)

     所以我们不妨试着将数组长度不断缩短。这里不妨提出一个引理。假设有两个有序数组am,bn,他们整合后的有序数组为cn+m。他们的中位数分别是Am/2,Bn/2,C(m+n)/2。如果Am/2 < Bn/2,则 A0…m/2 <= C(m+n)/2 <= Bn/2…n 。

     引理证明:

           假设 Am/2 > C(m+n)/2 ,那么 Bn/2  > C(m+n)/2,所以在数组Am里有大于m/2个数大于C(m+n)/2,在数组Bn里也有n/2个数大于C(m+n)/2

           也就是说在Cn+m里有(m+n)/2个数大于C(m+n)/2,此时就C(m+n)/2不再是数组Cn+m的中位数。

           所以A0…m/2 <= C(m+n)/2。

           同理可得C(m+n)/2 <= Cn/2…n 。

    根据上述引理,我们不妨设m>n,那么我们根据判断两个数组的中位数大小,每个数组每次减少n/2长度,直到n为1。如此,我们通过减少log(n)次可以得到答案。这种方法的时间复杂度是(log(min(m,n)))。

class Solution:
    def getMedian(self,nums):
        size = len(nums)
        if size == 0:
            return [0,0]
        if size % 2 == 1:
            return [nums[size//2],size//2]
        else:
            return [(nums[size//2 - 1] + nums[size//2])/2,size//2]
    
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        size1 = len(nums1) # ig longer
        size2 = len(nums2)
        if size1 < size2:
            return self.findMedianSortedArrays(nums2,nums1)
        m1 = self.getMedian(nums1)
        m2 = self.getMedian(nums2)
        if size2 == 0:
            return m1[0]
        if size2 == 1:
            if size1 == 1:
                return (m1[0] + m2[0])/2
            if size1 % 2 == 0:
                if nums2[0] < nums1[size1//2 - 1]:
                    return nums1[size1//2 -1]
                if nums2[0] > nums1[size1//2]:
                    return nums1[size1//2]
                else:
                    return nums2[0]
            else:
                if nums2[0] < nums1[size1//2 - 1]:
                    return (nums1[size1//2 - 1] + nums1[size1//2])/2
                if nums2[0] > nums1[size1//2 + 1]:
                    return (nums1[size1//2 + 1] + nums1[size1//2])/2
                else:
                    return (nums2[0] + nums1[size1//2])/2
        if size1 % 2 == 0:
            if size2 % 2 == 0:
                if nums1[size1//2 - 1] > nums2[size2//2 - 1] and nums2[size2//2] > nums1[size1//2]:
                    return m1[0]
                if nums1[size1//2 - 1] < nums2[size2//2 - 1] and nums2[size2//2] < nums1[size1//2]:
                    return m2[0]
        if m1[0] < m2[0]:
            return self.findMedianSortedArrays(nums1[m2[1]:],nums2[:size2 - m2[1]])
        if m1[0] > m2[0]:
            return self.findMedianSortedArrays(nums1[:size1 - m2[1]],nums2[m2[1]:])
        else:
            return m1[0]

到此,关于“Java怎么寻找两个有序数组的中位数”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联网站,小编会继续努力为大家带来更多实用的文章!


本文名称:Java怎么寻找两个有序数组的中位数
标题来源:http://myzitong.com/article/pjgode.html