思路

代码

class Solution {
    public double findMedianSortedArrays(int[] a, int[] b) {
        int l = a.length + b.length;
        if(l % 2 == 0){
            int left = find(a, 0, b, 0, l/2);
            int right = find(a, 0, b, 0, l/2 + 1);
            return (left + right)/2.0;
        }else{
            return find(a, 0, b, 0, l/2 + 1);
        }
    }

    public int find(int[] a, int ai, int[] b, int bj, int k){
        // 确保数组长度一定是较短的那个, 开始忘记写return
        if(b.length - bj < a.length - ai) return find(b, bj, a, ai, k);
        // 如果第一个数组是空的, 那么直接返回第二个数组的第k个元素, 因为k是长度/2的取值, 所以它是从1开始的, 因此这里第k个是bj + k - 1
        if(a.length == ai) return b[bj + k - 1];
        // 如果要找的数索引是1, 返回a,b中最小者即可
        // System.out.println("k == "+k+", ai=="+ai+", bj==" + bj);
        if(k == 1) return Math.min(a[ai], b[bj]);
        // a数组总是长度较小的那一个, 所以需要确保这里不会越界, 取一下ai+k/2与a.length的较小值
        int mi = Math.min(ai + k/2, a.length), mj = bj + k - k/2;
        if(a[mi - 1] < b[mj - 1]) return find(a, mi, b, bj, k-(mi-ai));
        else return find(a, ai, b, bj+k/2, k-k/2);
    }
}