Leetcode初学——寻找两个有序数组的中位数

题目：

因为这道题要求时间复杂度为O（log(m+n)），并且是让我们求中位数

所以可以初步判断题目中需要涉及到二分查找（如果不了解二分查找的可以自行搜索，本文不做累述）

做一张简单的原理图：

数组1的长度 n1=4                                              数组2的长度 n2=6

所以k=（4+6）/2=5；

我们对这两个数组，分别取一半，比较左半边最大的两个数的大小，舍去小的那一半

对剩下的数组继续切割比较，继续舍去3

所以可以找到第5个数 “4”，而n1+n2=10

所以中位数就是（4+5）/2=4.5；

将其转换为代码：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        if (n1>n2)
            return findMedianSortedArrays(nums2, nums1);
        int k = (n1 + n2 + 1)/2;
        int left = 0;
        int right = n1;
        while(left < right){
            int m1 = left +(right - left)/2;
            int m2 = k - m1;
            if (nums1[m1] < nums2[m2-1])
                left = m1 + 1;
            else
                right = m1;
        }
        int m1 = left;
        int m2 = k - left;
        int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1-1],
                         m2 <= 0 ? Integer.MIN_VALUE : nums2[m2-1]);
        if ((n1 + n2) % 2 == 1)
            return c1;
        int c2 = Math.min( m1 >= n1 ? Integer.MAX_VALUE :nums1[m1],
                         m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);
        return (c1 + c2) * 0.5;
        
    }
}

作者：powcai
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/shuang-zhi-zhen-by-powcai/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
           

 由于代码我是看着powcai大佬写的，所以这里直接贴上大佬的代码

大佬的代码非常简洁，最后的两段更是精髓，统一对很多特殊情况做了处理,如：

{},{1}

{1,2},{3,4}

{2},{-2,-1};

········

令人佩服不已