Java怎么尋找兩個有序數組的中位數

這篇文章主要介紹“Java怎么尋找兩個有序數組的中位數”，在日常操作中，相信很多人在Java怎么尋找兩個有序數組的中位數問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java怎么尋找兩個有序數組的中位數”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

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怎么尋找兩個有序數組的中位數”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！