一. 题目

二. 思路

三. 代码

class Solution
{
    /*
        a1是长度较短的数组，a2是长度较长的数组
        l是a1中没被排除的起始位置，可能为n或m
        r是a2中没被排除的起始位置
        k是在a1和a2中找第k小的数(从s1、s2开始算)
     */
    int tfind(int[] a1, int l, int[] a2, int r, int k)
    {
        if (a1.length - l > a2.length - r)//让剩余元素数量较少的在前面
            return tfind(a2, r, a1, l, k);
        if (a1.length == l) return a2[r + k - 1];//若a1为空
        if (k == 1) return Math.min(a1[l], a2[r]);//返回二者最小的一个数

        //sl和sr表示新的起始位置，要比的数是上一个，比输的排除
        int sl = Math.min(a1.length, l + k / 2), sr = Math.min(a2.length, r + k - k / 2);//sr是剩余的数就行，不一定非得一半
        if (a1[sl - 1] <= a2[sr - 1]) return tfind(a1, sl, a2, r, k - (sl - l));
        return tfind(a1, l, a2, sr, k - (sr - r));
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2)
    {
        int n = nums1.length, m = nums2.length, sum = n + m;
        if (sum % 2 != 0) return tfind(nums1, 0, nums2, 0, sum / 2 + 1);//奇数情况,初始有效起点都为0
        else
        {
            //偶数情况，初始有效起点都为0
            int k1 = tfind(nums1, 0, nums2, 0, sum / 2);
            int k2 = tfind(nums2, 0, nums1, 0, sum / 2 + 1);
            return (k1 + k2) / 2.0;
        }
    }
}