试水刷题，先从简单的练起。

题目

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

解题思路

把题目分为几部分思考就差不多了。

中位数

假设存在有序数列 arr[n] ：
n 为奇数时，中位数为 arr[(n + 1) / 2]
n 为偶数时，中位数为 (arr[n/2]+arr[n/2+1])/2
总而言之，我们的目标就是先找到第 x 个数就行了，或者说第 x 小的数字。
对于偶数的情况，其实就是第 x 个和第 x+1 个，没太大区别。

一次删一大半

找第 x 小的数字一个方法就是，把比它小的数字全都先删掉。
假设要找第 6 小的数字，那就要删掉 5 个，现在把两个有序数列排在一起，画个图示意一下：

图中，x 代表最小的 5 个数字，？代表比较大的其它数字。
由于两个数列自身是有序的，那么这 5 个 x 的分布也就这 6 种情况，实际上是互相对称的 3 组。
观察一下可以发现，在所有的情况中，都至少有一边的数列，包含了 3 个 x，另一边则数目不定。

简单推算一下可得：
如果你想删掉前 x 个数字，那么上下两个数列，其中一个的前 x/2 + x%2 位，一定被删。

好了，接下来可以根据这个推论，每次先删掉一大半的竞争者，等到都删完了，剩下的数列中，最小的数字就是我们的中位数了。

模拟一下

我们先构造一组测试数据：

1,4,5,7,12,17,19 和 3,6,9,15

老样子，示意图做一下，可以看到中位数毫无疑问的是第 6 个数字 7

因为总共有 11 个数字，那么中位数自然是第 6 个数字，也就是说，我们只要把比中位数小的 5 个数字，清理出队伍就算胜利。

因为要删 5 个数字，那么先从一边拿出来 3 个，很显然的是，肯定有一边我们拿多了。

怎么判断有没有拿多呢？拿多数字肯定比没拿多的大，所以只需要检查一下拿出来的两个数列里最后一个数的大小就好了。

很显然，1,4,5这个数列里全都是小弟，一波全都带走删掉。

第一轮清理之后，还有 2 个名额，老样子一边先分 1 个名额尝试清理掉。

很明显 3 需要被删掉。

继续删，最后一个小弟 6 被删掉，接下来就要进入决赛圈了。

决赛圈就没有删数这一说了，谁小谁就是我们要找的数。

模拟两下

虽然上面的测试样例已经尽可能构建的复杂，但是比较数组长度是奇数，偶数的话是两个数，会不会难一些呢？

接下来，我们构造另一组测试数据来试试看，前面的过程就不赘述了，直接上图：

可以看到，此时我们需要找的是第 6 和第 7 个数字，那只需要在找到第6个数字后，删掉它再找下一个就好了。

解答

Java 代码

class Solution {
    boolean need_two;
    int[] ans = new int[]{0, 0};

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //只有一个数字
        if (nums1.length + nums2.length == 1)
            return nums1.length == 1 ? nums1[0] : nums2[0];

        int len_sum = nums1.length + nums2.length;
        need_two = len_sum % 2 == 0;

        // 7 个数，中位数在第 4 个，跳过 3 个
        // 8 个数，中位数在第 4, 5 个，跳过 3 个，后面那个单独算
        int need_skip = (len_sum + len_sum % 2) / 2 - 1;

        if (nums1.length < nums2.length)
            find(need_skip, nums1, 0, nums2, 0);
        else
            find(need_skip, nums2, 0, nums1, 0);

        if (len_sum % 2 == 0)
            return (ans[0] + ans[1]) * 0.5;
        else
            return ans[1];
    }

    //第一个数组是 short，第二个是 long
    private void find(int need_skip, int[] nums_s, int right_s, int[] nums_l, int right_l) {
        // 先处理一下一个数列空掉的情况
        if (nums_s.length - right_s == 0) {
            ans[1] = nums_l[right_l + need_skip];
            if (need_two)
                ans[0] = nums_l[right_l + need_skip + 1];
            return;
        }

        if (need_skip == 0) {
            // 最小的那个就是最后的数字
            if (need_two) {
                need_two = false;

                if (nums_s[right_s] < nums_l[right_l]) {
                    ans[0] = nums_s[right_s];
                    right_s += 1;
                } else {
                    ans[0] = nums_l[right_l];
                    right_l += 1;
                }

                // 多算一轮
                if (nums_s.length - right_s <= nums_l.length - right_l)
                    find(0, nums_s, right_s, nums_l, right_l);
                else
                    find(0, nums_l, right_l, nums_s, right_s);

            } else {
                ans[1] = Math.min(nums_s[right_s], nums_l[right_l]);
            }
            return;
        }

        // 计算一下要删多少个
        int each_check = (need_skip + need_skip % 2) / 2;
        int skip_s = Math.min(nums_s.length - right_s, each_check);
        int skip_l = Math.min(nums_l.length - right_l, each_check);
        int check_s = nums_s[right_s + skip_s - 1];
        int check_l = nums_l[right_l + skip_l - 1];

        if (check_s < check_l) {
            //删第一个数列
            right_s += skip_s;
            need_skip -= skip_s;
        } else {
            //删第二个数列
            right_l += skip_l;
            need_skip -= skip_l;
        }

        // find 下一轮
        if (nums_s.length - right_s <= nums_l.length - right_l)
            find(need_skip, nums_s, right_s, nums_l, right_l);
        else
            find(need_skip, nums_l, right_l, nums_s, right_s);
    }
}

代码写的比较粗糙，基本上是想到什么就写什么，应该有一些重复的地方还可以做优化，好在跑出来效果还算不错。