难度困难4868
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4] 输出：2.50000 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：
输入：nums1 = [0,0], nums2 = [0,0] 输出：0.00000
示例 4：
输入：nums1 = [], nums2 = [1] 输出：1.00000
示例 5：
输入：nums1 = [2], nums2 = [] 输出：2.00000
提示：
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106 二：思路讲解
创建两个堆 一个大顶堆 一个小顶堆 让两个数组平均的放到两个堆中 那么 小顶堆的顶堆是该堆最大值 大顶堆的顶堆是该堆最小值 如果两个堆数据量不相同 取堆容量大的堆顶 如果两个堆数量相同 取两个堆顶的平均值 你品.......你想........你仔细韵味一下三：Java代码
public class LeetCode4 {
public static void main(String[] args) {
int[] arr1 = {1, 3, 5, 6};
int[] arr2 = {2, 4,};
System.out.println(model(arr1, arr2));
}
private static double model(int[] arr1, int[] arr2) {
// 创建大顶堆、创建小顶堆
PriorityQueue max = new PriorityQueue<>();
// 堆顶是最大值 则为小顶堆 需要逆序
PriorityQueue min = new PriorityQueue<>((o1, o2) -> o2 - o1);
// 添加元素到堆中
int arr1Len = addElement(max, min, arr1, 0);
int totalLen = addElement(max, min, arr2, arr1Len);
return findMedianSortedArrays(max, min, totalLen);
}
private static int addElement(PriorityQueue max, PriorityQueue min, int[] arrs, int num) {
for (int e : arrs) {
if (num++ % 2 == 0) {
min.add(e);
max.add(min.poll());
} else {
max.add(e);
min.add(max.poll());
}
}
return num;
}
public static double findMedianSortedArrays(PriorityQueue max, PriorityQueue min, int num) {
// 如果两个堆数据量不相同 取堆容量大的堆顶
//如果两个堆数量相同 取两个堆顶的平均值
if (num % 2 != 0) {
return (double) max.peek();
} else {
return (max.peek() + min.peek()) / 2.0;
}
}
}
