4. 寻找两个有序数组的中位数

这几天在看Jetpack全家桶，被搞的有点自闭，没时间到LeetCode上玩耍，晚上在看的官方的demo的时候，yyb滴滴了我一下

？看什么看，看Jetpack全家桶不好吗？？？
好吧既然余总叫小的看一下，我就看看吧

这...怎么这模板这么眼熟，果然，在LeetCode上找到了他嘴里的她，于是就有了下面的故事...

寻找两个有序数组的中位数

题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

---

示例：

nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

---

提示：你可以假设 nums1 和 nums2 不会同时为空。

转载来源：力扣（LeetCode）

---

题目分析

解法一：

因为中位数是有序数组中间的那个数（或者两个数的平均数），而题目明确是求两个有序数组的中位数，这就很容易就想到将两个有序数组归并，然后求出他们的中位数；
两个有序数组合并的时间复杂度是O(M+N)，显然不符合题目的要求，但是提交上去竟然过了；
注：解法一里用了栈来收集前n/2的数字，到达中位数的时候停下来，返回

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1=0;
        int len2=0;
        int len=nums1.length+nums2.length;
        Stack<Integer> stack=new Stack<>();
        while(stack.size()<=len/2) {
            if (len1 < nums1.length && len2 < nums2.length) {
                if (nums1[len1] <= nums2[len2]) {
                    stack.push(nums1[len1++]);
                    System.out.println(nums1[len1-1]);
                } else {
                    stack.push(nums2[len2++]);
                    System.out.println(nums2[len2-1]);
                }
            } else if (len1 == nums1.length) {
                stack.push(nums2[len2++]);
                System.out.println(nums2[len2-1]);
            } else if (len2 == nums2.length) {
                stack.push(nums1[len1++]);
                System.out.println(nums1[len1-1]);
            }
        }
        if(len%2==0){
            double a=stack.pop();
            double b=stack.pop();
            return ((a+b)/2);
        }else{
            return (double)(stack.pop());
        }
    }

解法二：

看到log，其实我们想到的应该是二分， 下面我用图解的方式更好的展示一下二分的思路

1. 这是原始状态的数组，满足题目中的两个有序数组的条件

   
   1

2. 分别将两个数组砍成两半，现在假设两个左边是合并有序数组的左边，两个右边是合并有序数组的右边，有序数组显然有这样的性质：左边的数小于右边的数，现在我们验证一下我们的假设时候满足这样的性质
   

   2

3. 验证：我们先找出左边最大的数，它是5，再找出右边最小的数，它是2，显然不满足有序数组的性质，这可怎么办呢？快排里有个很重要的思想，就是给每一个数找到属于它的位置，我们这里可以受快排的启发，给不符合性质的数找到属于它的位置：把5放到右边去，把2放到左边去！

   
   3

4. 现在数组变成这个样子，左边最大的是2，右边最小的是5，显然满足题目的意思

   
   4

5. 3和4是一种情况，是上面数组的左边大于下面数组的右边，还有另一种情况，就是下面数组的左边大于上面数组的右边，如下所示：

   
   5

6. 对于5的情况，做法和（3、4）差不多，将3放到左边，将5放到右边，这样假设就成立了！

   
   6

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //确保num1比nums2要短
        if (nums1.length > nums2.length)
            return findMedianSortedArrays(nums2, nums1);

        //特殊情况的处理，短的为空，直接返回长的中位数
        if (nums1.length == 0)
             if( nums2.length % 2 == 0)
                return (nums2[nums2.length / 2] + nums2[nums2.length / 2 - 1]) / 2.0;
             else
                 return nums2[nums2.length / 2];

        //将短的数组分成两半，长的数组也分成两半，
        //左边的大小 = 右边的大小（总长度为偶数） 或者左边大小 = 右边大小 - 1（总长度为奇数）
        int divide1 = nums1.length / 2;
        int divide2 = (nums1.length + nums2.length) / 2 - divide1;

        while (true) {
            //短的数组全都分到左边去
            if (divide1 == nums1.length) {
                //讨论奇偶数情况
                if ((nums1.length + nums2.length) % 2 == 0) {
                    //特殊情况：长的数组全都分到右边去
                    if (divide2 != 0)
                        return ((double) (Math.max(nums1[divide1 - 1], nums2[divide2 - 1]) + nums2[divide2])) / 2;
                    return (double) (nums1[divide1 - 1] + nums2[divide2]) / 2;
                } else {
                    return (double) nums2[divide2];
                }
            }
            //找出左边最大的和右边最小的
            int maxLeft, minRight;
            //短的全在右边
            if (divide1 == 0)
                maxLeft = nums2[divide2 - 1];
            else
                maxLeft = Math.max(nums1[divide1 - 1], nums2[divide2 - 1]);

            //长的全在左边
            if (divide2 == nums2.length)
                minRight = nums1[divide1];
            else
                minRight = Math.min(nums1[divide1], nums2[divide2]);
            //符合假设，直接返回
            if (minRight >= maxLeft)
                if ((nums1.length + nums2.length) % 2 == 0)
                    return ((double) (minRight + maxLeft)) / 2;
                else
                    return (double) minRight;
                
            // 不符合假设，左边最大的右移，右边最小的左移
            // 分别对应上右<下左 ||  下右<上左
            if (nums1[divide1] <= nums2[divide2 - 1]) {
                divide1++;
                divide2--;
            } else {
                divide1--;
                divide2++;
            }
        }
    }

代码文件

---