题目

给定两个大小分别为 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

解题

解法1

中位数（又称中值，英语：Median），统计学中的专有名词，代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分。

所以我们只需要将数组进行切。

一个长度为 m 的数组，有 0 到 m 总共 m + 1 个位置可以切。

我们把数组 A 和数组 B 分别在 i 和 j 进行切割。

将 i 的左边和 j 的左边组合成「左半部分」，将 i 的右边和 j 的右边组合成「右半部分」。

当 A 数组和 B 数组的总长度是偶数时，如果我们能够保证

1、左半部分的长度等于右半部分，i + j = m - i + n - j , 也就是 j = ( m + n ) / 2 - i

2、左半部分最大的值小于等于右半部分最小的值 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））。那么，中位数就可以表示（左半部分最大值 + 右半部分最小值）/ 2 。（max ( A [ i - 1 ] , B [ j - 1 ]）+ min ( A [ i ] , B [ j ]）） / 2

当 A 数组和 B 数组的总长度是奇数时，如果我们能够保证

1、左半部分的长度比右半部分大 1，i + j = m - i + n - j + 1也就是 j = ( m + n + 1) / 2 - i

2、左半部分最大的值小于等于右半部分最小的值 max ( A [ i - 1 ] , B [ j - 1 ]）） <= min ( A [ i ] , B [ j ]））。那么，中位数就是左半部分最大值，也就是左半部比右半部分多出的那一个数。max ( A [ i - 1 ] , B [ j - 1 ]）

代码

/*** @author zxn* @ClassName Median* @Description* @createTime 2023年05月29日 19:06:00*/
public class Median {// 输入：nums1 = [1,3], nums2 = [2]//输出：2.00000//解释：合并数组 = [1,2,3] ，中位数 2// 输入：nums1 = [1,2], nums2 = [3,4]//输出：2.50000//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5public static void main(String[] args) {int[] nums1 = {1, 2}, nums2 = {3, 4};System.out.println("--->" + findMedianSortedArrays(nums1, nums2));}public static double findMedianSortedArrays(int[] arr1, int[] arr2) {int m = arr1.length;int n = arr2.length;if (m > n) {return findMedianSortedArrays(arr2, arr1);}int iMin = 0;int iMax = m;while (iMin <= iMax) {int i = (iMin + iMax) / 2;int j = (m + n + 1) / 2 - i;if (i != m && j != 0 && arr2[j - 1] > arr1[i]) {iMin = i + 1;} else if (i != 0 && j != n && arr1[i - 1] > arr2[j]) {iMax = i - 1;} else {int leftMax = 0;if (i == 0) {leftMax = arr2[j - 1];} else if (j == 0) {leftMax = arr1[i - 1];} else {leftMax = Math.max(arr1[i - 1], arr2[j - 1]);}if ((m + n) % 2 == 1) {return leftMax;}int rightMin = 0;if (i == m) {rightMin = arr2[j];} else if (j == n) {rightMin = arr1[i];} else {rightMin = Math.min(arr1[i], arr2[j]);}return (leftMax + rightMin) / 2.0;}}return 0;}
}