题解 | 牛的体重排序

import java.util.*;


public class Solution {
    private int n;
    private int m;

    public double findMedianSortedArrays (int[] weightsA, int[] weightsB) {
        this.m = weightsA.length;
        this.n = weightsB.length;
        if (((m + n) & 1) == 1) {
            // find 1 + ((m + n) >> 1)
            return getKthInTwoArray(weightsA, weightsB, 1 + ((m + n) >> 1));
        } else {
            // find 1 + ((m + n) >> 1)
            // find ((m + n) >> 1)
            return 0.5d * (getKthInTwoArray(weightsA, weightsB, 1 + ((m + n) >> 1)) + getKthInTwoArray(weightsA, weightsB, (m + n) >> 1));
        }
    }

    private double getKthInTwoArray(final int[] a, final int[] b, int k) {
        int i = 0, j = 0;
        while (true) {
            if (i == m) {
                return b[j + k - 1];
            }
            if (j == n) {
                return a[i + k - 1];
            }
            if (k == 1) {
                return Math.min(a[i], b[j]);
            }
            final int maxi = Math.min(i + k / 2 - 1, m - 1);
            final int maxj = Math.min(j + k / 2 - 1, n - 1);
            if (a[maxi] <= b[maxj]) {
                k -= maxi - i + 1;
                i = maxi + 1;
            } else {
                k -= maxj - j + 1;
                j = maxj + 1;
            }
        }
    }
}