Leetcode 4. Median of Two Sorted Arrays

Median of Two Sorted Arrays :

題目的輸入為兩組已經排序過的陣列（由小到大），而我們的目標就是回傳中間值。

• 若陣列的總長度為奇數，則回傳中央的值
• 若陣列的總長度為偶數，則回傳中央兩值加總的平均

時間複雜度: O(1)

空間複雜度: O(1)

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums1+=nums2
        nums1.sort()
        med=nums1[(len(nums1)-1)//2]
        if len(nums1)%2==1:              #陣列的總長度為奇數
            return med
        else:                            #陣列的總長度為偶數
            l=nums1[(len(nums1)-1)//2]
            r=nums1[((len(nums1)-1)//2)+1]
            return (l+r)/2               #中央兩值加總的平均

C++

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        const int n1 = nums1.size();
        const int n2 = nums2.size();
        #保證n1大於n2
        if (n1 > n2) return findMedianSortedArrays(nums2, nums1);
        # 中位數
        const int k = (n1 + n2 + 1) / 2;
 
        int l = 0;
        int r = n1;
        
        # 遞歸
        while (l < r) {
            const int m1 = l + (r - l) / 2;  # m1長度
            const int m2 = k - m1;           # m2長度
            if (nums1[m1] < nums2[m2 - 1])   # m1 數組數量太少
                l = m1 + 1;                  
            else                             # m2 數組數量太少
                r = m1;
        }
        
        const int m1 = l;
        const int m2 = k - l;
        
        #m1 <= 0 第一個數組沒使用
        const int c1 = max(m1 <= 0 ? INT_MIN : nums1[m1 - 1], 
                           m2 <= 0 ? INT_MIN : nums2[m2 - 1]);
        #奇數
        if ((n1 + n2) % 2 == 1)
            return c1;    
        #右中位數
        const int c2 = min(m1 >= n1 ? INT_MAX : nums1[m1], 
                           m2 >= n2 ? INT_MAX : nums2[m2]);
                
        return (c1 + c2) * 0.5;
    }
};