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