leetcode|leetcode 4. Median of Two Sorted Arrays 寻找两个正序数组的中位数(困难) leetcode4.MedianofTwoSortedArrays寻找

一、题目大意标签: 查找
https://leetcode.cn/problems/median-of-two-sorted-arrays
【leetcode|leetcode 4. Median of Two Sorted Arrays 寻找两个正序数组的中位数(困难)】给定两个大小分别为 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

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

二、解题思路号称leetcode守门员的题。中位数可以来自于同一个数组，也可以来自于两个数组，可以是一个数，也可以是两个数。
实现思路（参考花花酱的讲解）
分类：

leetcode|leetcode 4. Median of Two Sorted Arrays 寻找两个正序数组的中位数(困难)

文章图片

思路：假设n1,n2是两个数组的元素，那么k=(n1+n2+1)/2就表示左中位数或中位数的索引，假设从nums1中取m1个元素，从nums2中取m2个元素，那么m1+m2 = k。我们要求的中位数就是从max(nums[m1-1], nums[m2-1])和min(nums[m1], nums[m2])。

文章图片

文章图片

三、解题方法 3.1 Java实现

public class Solution2 { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int n1 = nums1.length; int n2 = nums2.length; // 对长度小的数组做二分搜索 if (n1 > n2 ) { return findMedianSortedArrays(nums2, nums1); }// 偶数情况：nums1=>[1, 2, 3] nums2=>[3, 4, 5]中位数 2 3 // 奇数情况：nums1=>[1, 2, 3] nums2=>[2, 3, 4, 5] 中位数 3 // nums1=>[-1, 1, 3, 5, 7, 9] nums2=>[2, 4, 6, 8, 10, 12, 14, 16] int l = 0; int r = n1; // 偶数情况：左中位数奇数情况：中位数 int k = (n1 + n2 + 1) / 2; while (l < r) { int m1 = l + (r - l) / 2; int m2 = k - m1; if (nums1[m1] < nums2[m2-1]) { l = m1 + 1; } else { r = m1; } } int m1 = l; int m2 = k - l; int c1 = Math.max(m1 < 1 ? Integer.MIN_VALUE : nums1[m1-1], m2 < 1 ? Integer.MIN_VALUE : nums2[m2-1]); // 奇数情况 if ((n1 + n2) % 2 == 1) { return c1; }int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1], m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]); return (c1 + c2) * 0.5; } }

四、总结小记