Leetcode 4 Median of Two Sorted Arrays

思路： 这道题要求时间复杂度是log，所以很容易想到要用binary search。但是这题实在是太难了，我没想到怎么做。直到看到这个youtube视频我才恍然大悟：链接。这题我们需要充分利用两个数组已经是sorted的条件，然后最重要的就是要理解中位数的意义。那中位数怎么求？在一个sorted的array中，中位数就是：中位数之前的数字都比他小，之后的数字都比他大，而且左右两边的数字个数要一样多。那么放在这题上，我们有两个已经sorted好的数组，那我们只需要在x数组切一刀，再在y数组切一刀，这两刀都把两个数组分成了两部分。这时候我们要保证两点，一是x的左半部分+y的左半部分的数字个数 = x的右半部分 + y的右半部分的数字个数（满足中位数性质，即最中间的数）；二是要保证左半边的数字都小于右半边的数字（也是中位数的性质）。找到这样的两个切割点，那我们最后要求的中位数就取决于这两个切割点了。至于这边不断寻找切割点的方法就是binary search。具体思路看我上面给的视频链接，讲的很详细，下面直接上代码：

// 讲解视频链接：https://www.youtube.com/watch?v=LPFhl65R7ww&t=1013s

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length){
            return findMedianSortedArrays(nums2,nums1);
        }
        int x = nums1.length;
        int y = nums2.length;
        int low = 0;
        int high = x;
        
        while(low <= high){
            int partitionX = (low + high) / 2;
            int partitionY = (x + y + 1) / 2 - partitionX; // 满足中位数第一个性质（左右两边个数相等）
            
            int xLeftMax = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int xRightMin = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
            int yLeftMax = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int yRightMin = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
            
            if(xLeftMax <= yRightMin && yLeftMax <= xRightMin){ // 满足中位数第二个性质（左边的都比右边的小）
                if((x + y) % 2 == 0){
                    return ((double)Math.max(xLeftMax,yLeftMax) + Math.min(xRightMin,yRightMin)) / 2;
                }else{
                    return (double)Math.max(xLeftMax,yLeftMax);
                }
            }else if(xLeftMax > yRightMin){ // 当前的切割点不正确，二分法寻找下一个切割点
                high = partitionX - 1;
            }else{ // 当前的切割点不正确，二分法寻找下一个切割点
                low = partitionX + 1;
            }
        }
        return 0.0;
    }
}

总结：

1. 要求时间复杂度为log，第一要想到binary search
2. 要彻底了解中位数的意义