Leetcode - Median of Two Sorted Arrays

Question

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

Java Code

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    return (nums1.length > nums2.length) ? binarySearch(nums1, nums2) : 
        binarySearch(nums2, nums1);         
}

//要求數組nums1為較長的數組
public double binarySearch(int[] nums1, int[] nums2) {  
    //設定兩個數組的各個初始指針
    int min1 = ;
    int max1 = nums1.length - ;
    int med1 = max1/;//如果數組長度為偶數，則中位數指針總是指向下标較小的那個元素
    int min2 = ;
    int max2 = nums2.length - ;
    int med2 = max2/;

    //每一輪二分查找後兩個數組均需要裁剪掉的長度，為什麼總是nums2數組的一半長度？
    int remove = (max2 - min2)/;

    //case 0: 數組nums2為空數組，直接傳回數組nums1的中位數
    if(max2 == -) {
        if((nums1.length & ) == )
            return (nums1[nums1.length/] + nums1[nums1.length/ - ])/; 
        else
            return nums1[nums1.length/];
    }

    //case 1: 數組nums2超過2個元素
    while(max2 - min2 > ) {
        //如果目前的nums1和nums2的中位數正好相等，且在融合後的數組中也是中位數
        if(nums1[med1] == nums2[med2] && med1 + med2 +  == (nums1.length + nums1.length + )/)
            return (nums1[med1] + nums2[med2])/;
        //把目前nums1數組的低位區間和目前nums2數組的高位區間裁剪掉
        else if(nums1[med1] < nums2[med2]) {
            min1 += remove;
            max2 -= remove;
        //把目前nums1數組的高位區間和目前nums2數組的低位區間裁剪掉    
        }else {
            max1 -= remove;
            min2 += remove;
        }
        //更新兩個數組的中位數指針以及下一輪需要裁剪掉的長度
        med1 = (min1 + max1)/;
        med2 = (min2 + max2)/;
        remove = (max2 - min2)/;
    }

    //case 2: 數組nums2剩2個元素
    if(max2 - min2 == ) {
        //case 2.1: nums1剩2個元素
        if(max1 - min1 == ) {
            return (Math.max(nums1[min1], nums2[min2]) + Math.min(nums1[max1], nums2[max2]))/;
        //case 2.2: 數組nums1至少剩餘3個元素
        }else {
            if(((max1 - min1) & ) == ) {//case 2.2.1: 數組nums1剩餘奇數長度
                if(nums1[med1] <= nums2[med2]) {
                    min1++;
                    max2--;//下一步轉到case 3.3.2
                }else {
                    if(nums2[med2 + ] <= nums1[med1])
                        return Math.max(nums2[med2 + ], nums1[med1 - ]);
                    else 
                        return nums1[med1];
                }
            }else {//case 2.2.2: 數組nums1剩餘偶數長度
                if(nums1[med1] <= nums2[med2]) {
                    if(nums2[med2 + ] < nums1[med1 + ])//特殊情況
                        return (nums2[med2] + nums2[med2 + ])/;
                    else {
                        min1++;
                        med1++;//pay attention to this
                        max2--;//下一步轉到case 3.3.1
                    }
                }else {
                    if(nums2[med2 + ] <= nums1[med1])
                        return (nums1[med1] + Math.max(nums2[med2 + ], nums1[med1 - ]))/;
                    else
                        return (nums1[med1] + Math.min(nums2[med2 + ], nums1[med1 + ]))/;
                }
            }
        }
    }

    //case 3: 數組nums2剩1個元素
    if (max2 == min2) {
        //case 3.1: 數組nums1剩1個元素
        if(max1 == min1);
        //case 3.2: 數組nums1剩2個元素
        else if(max1 - min1 == ) {
            return  Math.min(Math.max(nums1[min1], nums2[min2]), nums1[max1]);
        //case 3.3: 數組nums1至少剩3個元素
        }else {
            if((max1 - min1 & ) == ) {//case 3.3.1: 數組nums1剩餘奇數長度
                if(nums1[med1] < nums2[med2]) {
                    if(nums2[med2] > nums1[med1 + ])
                        return (nums1[med1] + nums1[med1 + ])/;
                }else if(nums1[med1] > nums2[med2]) {
                    if(nums2[med2] < nums1[med1 - ])
                        return (nums1[med1] + nums1[med1 - ])/;
                }else
                    return nums1[med1];
            }else {//case 3.3.2: 數組nums1剩餘偶數長度 
                if(nums1[med1] < nums2[med2])
                    return Math.min(nums2[med2], nums1[med1 + ]);
                else
                    return nums1[med1];
            }
        }
    }
    return (nums1[med1] + nums2[med2])/;
}
           

說明

• 本文給的算法貌似達到了O(log(min(m, n)))，優于本題要求的O(log(m+n))？
• 本題在Leetcode上屬于難度系數最高的Hard級别，對我來說的确是非常的有挑戰性！之前和教研室小夥伴做了一個晚上也沒搞定，不過經過仔細分析也找到了一些初步的解決思路，但是還有一些細節問題沒有很好地解決。今天花了很多時間，不斷地踩坑。。填坑。。踩坑。。填坑，最終總算AC了，不過runtime隻排到40%左右，怎麼這麼低啊。。。
• 整個代碼的核心思想主要展現在while循環中，由于求中位數必須區分數組為奇數和偶數時的不同，是以需要多層if-else來分情況讨論，具體的算法思想和實作細節下次再具體寫吧（其實注釋裡說得大概差不多了）。另外昨天看到有一個非常棒的算法來解決本題，這裡貼出部落格連結，供大家參考學習。