LeetCode題目4. 尋找兩個有序數組的中位數

給定兩個大小為 m 和 n 的有序數組 nums1 和 nums2。

請你找出這兩個有序數組的中位數，并且要求算法的時間複雜度為 O(log(m + n))。

你可以假設 nums1 和 nums2 不會同時為空。

示例1

nums1 = [1, 3]

nums2 = [2]

則中位數是 2.0

示例2

nums1 = [1, 2]

nums2 = [3, 4]

則中位數是 (2 + 3)/2 = 2.5

解題思路

思路1：利用兩個指針left和right，right指針對兩個數組的較小的元素做向後周遊，left指針存取right上一步的值。當兩個數組長度和為奇數時，right即為所求；當長度和為偶數時，結果為（left+right）/2

思路2： 思路1的時間複雜度為O(m+n)，為了能夠降低時間複雜度，是以有了利用二分法的思路2

完整代碼

思路1

class Solution1 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if((nums1==null||nums1.length==0)&&(nums2==null||nums2.length==0)) return 0;
        if(nums1==null||nums1.length==0) {
            int mid=nums2.length/2;
            int shang=nums2.length%2;
            if(shang==0)
                return (nums2[mid]+nums2[mid-1])/2.0;
            else return nums2[mid];
        }
        if(nums2==null||nums2.length==0) {
            int mid=nums1.length/2;
            int shang=nums1.length%2;
            if(shang==0)
                return (nums1[mid]+nums1[mid-1])/2.0;
            else return nums1[mid];
        }
        int len1=nums1.length;
        int len2=nums2.length;
        int len=len1+len2;
        int pa=0;
        int pb=0;
        int left=-1;
        int right=-1;
        for(int i=0;i<=len/2;i++){
            left=right;
            if(pa<len1&&(pb==len2||nums1[pa]<=nums2[pb]))
                right=nums1[pa++];
            else
                right=nums2[pb++];
        }
        if((len&1)==0) return (left+right)/2.0;
        return right;
        
    }
}
           

思路2

/**
 *      A[0] A[1] ...A[i-1] | A[i] A[i+1]... A[m-1]
 * B[0] B[1] B[2] ...B[j-1] | B[i] B[i+1]... B[n-1]
 */
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if((nums1==null||nums1.length==0)&&(nums2==null||nums2.length==0)) return 0;
        if(nums1==null||nums1.length==0) {
            int mid=nums2.length/2;
            int shang=nums2.length%2;
            if(shang==0)
                return (nums2[mid]+nums2[mid-1])/2.0;
            else return nums2[mid];
        }
        if(nums2==null||nums2.length==0) {
            int mid=nums1.length/2;
            int shang=nums1.length%2;
            if(shang==0)
                return (nums1[mid]+nums1[mid-1])/2.0;
            else return nums1[mid];
        }
        int m=nums1.length;
        int n=nums2.length;
        //使m的長度不大于n
        if(m>n)
            return findMedianSortedArrays(nums2, nums1);
        int iMin=0;
        int iMax=m;//注意這裡的IMax初始值是m而不是m-1
        while(iMin<=iMax)
        {
            int i=iMin+(iMax-iMin)/2;
            int j=(m+n+1)/2-i;//i和j滿足關系式    i+j==(m+n+1)/2-i;
            if(i!=0&&j!=n&&nums1[i-1]>nums2[j]){
                iMax=i-1;
            }
            else if(j!=0&&i!=m&&nums2[j-1]>nums1[i]){
                iMin=i+1;
            }
            else{
                int maxLeft=0;
                if(i==0){
                    maxLeft=nums2[j-1];
                }
                else if(j==0)
                    maxLeft=nums1[i-1];
                else 
                    maxLeft=Math.max(nums2[j-1],nums1[i-1]);
                 //當總長度為奇數時，直接傳回maxLeft
                if((m+n)%2==1) return maxLeft;
					
				//當總長度為偶時，要去計算minRight
                 int minRight=0;
                 if(i==m){
                    minRight=nums2[j];
                }
                else if(j==n)
                    minRight=nums1[i];
                else 
                    minRight=Math.min(nums2[j],nums1[i]);                                
                return (minRight+maxLeft)/2.0;
            }
        }
        return 0.0;
    }
}
           

參考

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/

更多LeetCode題目及答案解析見GitHub： https://github.com/on-the-roads/LeetCode

劍指offer題目及答案解析：https://github.com/on-the-roads/SwordToOffer