力扣 4. 寻找两个正序数组的中位数

本文主要是介绍力扣 4. 寻找两个正序数组的中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

好久不做题，脑子都木了

题目链接

这道题需要有技巧的二分

首先确认一下中位数的含义：表示在有序数列中处于中间位置的数，于是有两个性质：

• 位于中位数左右两侧的数应该满足 数量相等 这一要求。
• LeftMax < RightMin，也就是左侧最大的数要小于右侧最小的数。

现在我们有两个数组 $A$ 和 $B$，如果我们在 $A$ 数组查找到了第 $i$ 个数，那么为了满足 数量相等 条件，$B$ 数组中的查找位置 $j$ 是可以确定的，也就是 $j=\frac{m+n+1}{2}-i$（整数除法）。这里要注意一个点，$A$ 必须是较短的那个数组，否则可能 $j$ 会出现负数。

现在我们来尝试确定如何进行二分。已知 $A[i-1]<A[i]$, $B[j-1]<B[j]$

1. 若 $A[i-1]>B[j]$，则不满足 LeftMax < RightMin，于是 $i$ 应该左移，也就是修改右端点
2. 若 $A[i-1]<B[j]$，则修改左端点
3. 若 $A[i-1]=B[j]$，可以合并到上面两种情况中去。

最后的答案根据数组的奇偶性分为两种：

• 若为奇数则答案是 LeftMax
• 若为偶数则答案是 (LeftMax + RightMin) / 2

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {if (nums1.length > nums2.length) {return findMedianSortedArrays(nums2, nums1);}int m = nums1.length;int n = nums2.length;int left = 0, right = m;int leftMax = 0, rightMin = 0;while (left <= right) {int i = (left + right) / 2;int j = (m + n + 1) / 2 - i;int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);int nums_i   = (i == m ? Integer.MAX_VALUE : nums1[i]);int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);int nums_j   = (j == n ? Integer.MAX_VALUE : nums2[j]);if (nums_im1 < nums_j) {leftMax = Math.max(nums_im1, nums_jm1);rightMin = Math.min(nums_i, nums_j);left = i + 1;} else {right = i - 1;}}if ((m + n) % 2 == 0) return (leftMax + rightMin) / 2.0;return leftMax;}
}

这篇关于力扣 4. 寻找两个正序数组的中位数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---