题解 | #三个牛群中位数#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param herd1 int整型一维数组
     * @param herd2 int整型一维数组
     * @param herd3 int整型一维数组
     * @return double浮点型
     */
    public double findMedianSortedArray (int[] herd1, int[] herd2, int[] herd3) {
        // write code here
        int totalLength = herd1.length + herd2.length + herd3.length;
        herd1 = (herd1.length == 0) ? new int[] {Integer.MAX_VALUE} : herd1;
        herd2 = (herd2.length == 0) ? new int[] {Integer.MAX_VALUE} : herd2;
        herd3 = (herd3.length == 0) ? new int[] {Integer.MAX_VALUE} : herd3;
        if (totalLength % 2 == 1) {
            return findKthElem(herd1, herd2, herd3, totalLength / 2 + 1);
        } else {
            return (findKthElem(herd1, herd2, herd3, totalLength / 2) + findKthElem(herd1,
                    herd2, herd3, totalLength / 2 + 1)) / 2.0;
        }
    }
    //通过二分查找来确定小于或等于目标值的元素数量，以达到高效的计算目的。
    private static double findKthElem(int[] herd1, int[] herd2, int[] herd3,
                                      int k) {
        int low = Math.min(herd1[0], Math.min(herd2[0], herd3[0]));
        int high = Math.max(herd1[herd1.length - 1], Math.max(herd2[herd2.length - 1],
                            herd3[herd3.length - 1]));
        while (low < high) {
            int mid = low + (high - low) / 2;
            int count = countLessOrEqual(herd1, mid) + countLessOrEqual(herd2,
                        mid) + countLessOrEqual(herd3, mid);
            if (count < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
    private static int countLessOrEqual(int[] nums, int target) {
        int count = 0;
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                count = mid + 1;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return count;
    }
}