题解 | #三个牛群中位数#
三个牛群中位数
https://www.nowcoder.com/practice/8bc0369faf7c4ac5ab336f38e859db05
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; } }