欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

4. Median of Two Sorted Arrays

程序员文章站 2022-03-03 09:05:11
...

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

You may assume nums1 and nums2 cannot be both empty.

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

解法:

二分查找,我是按照youtube上花花酱的方法做的。找出leftMax1,leftMax2,rightMin1,rightMin2四个数进行判断,确保左右两边的数的数量等于k/2个。这题关键的点在于,如果到达corner case的时候怎么处理?查阅了很多个解法,发现只要将边界值附上inf和-inf即可避免讨论所有的情况,非常优雅。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
        int len1 = nums1.length;
        int len2 = nums2.length;
        int n = len1+len2;
        int odd = 0;
        if(n%2==1)odd=1;

        if(len2<len1){
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }

        if(nums1.length == 0 ){
            if(odd == 0)return (nums2[(nums2.length-1)/2]+nums2[(nums2.length)/2]+0.0)/2;
            else return nums2[nums2.length/2]+0.0;
        }

        //计算初始nums1的切分点,再根据k计算出nums2的切分点
        //判断leftMax1是否小于rightMin2,leftMax2是否小于rightMin1
        int left = 0;
        int right = nums1.length;
        int pivot = (left+right+1)/2;
        int below = (n+1)/2 - pivot;

        while(left<=right){

            int leftMax1 = pivot>0? nums1[pivot-1]:Integer.MIN_VALUE;
            int rightMin1 = pivot==nums1.length? Integer.MAX_VALUE:nums1[pivot];
            int leftMax2 = below>0? nums2[below-1]:Integer.MIN_VALUE;
            int rightMin2 = below==nums2.length? Integer.MAX_VALUE:nums2[below];

            if(leftMax1<=rightMin2 && leftMax2<=rightMin1){
                if(odd == 0){
                    return (Math.max(leftMax1,leftMax2)+Math.min(rightMin1,rightMin2)+ 0.0)/2 ;
                }else{
                    return Math.max(leftMax1,leftMax2);
                }
            }

            //移位
            if(leftMax1<=rightMin2 && leftMax2>rightMin1){
                left = pivot+1;
                pivot = (left+right)/2;
                below = (n+1)/2 - pivot;
            }else if (leftMax1>rightMin2 && leftMax2<=rightMin1){
                right = pivot;
                pivot = (left+right)/2;
                below = (n+1)/2 - pivot;
            }

        }

        return 0.0;
    }
}