题目链接
题目简介
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
示例 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
题目解析
- 题目要求的时间复杂度为
O(Log(m + n))，也就是指明了该算法只能使用二分查找 - 我们假设
num1的数组长度为 m，num2的数组长度为n
- 如果
m + n为偶数的话，那么中位数 = （m + n）/ 2 相当于 (m + n + 1) / 2 - 如果
m + n为奇数的话，那么中位数 = （m + n + 1）/ 2
- 我们定义 i 和 j 分别指向我们的 num1 和 num2
i初始值为我们num1的中位数，j初始值为我们num2的中位数
- 我们需要找到这样的一根假想线，且
线左边的数值小于线右边的数值，也相当于num1[i - 1] <= num2[j] && num2[j - 1] <= num1[i]，满足这个条件，既可以找到我们的中位数
- 最后，我们只需要根据
m + n的奇偶性，来得出最后的中位数即可
题目代码
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 交换下数组的值，让小一点的数组在上面 if(nums1.length > nums2.length){ int[] temp = nums1; nums1 = nums2; nums2 = temp; } int len1 = nums1.length; int len2 = nums2.length; // 求出两个数组的中位数 int toall = (len1 + len2 + 1) / 2; int left = 0; int right = len1; while(left < right){ // 这里为什么要 right + left + 1 ？ // 如果我们写 right + left // 假设 left = 4, right = 5 // 这种的话，i 一直等于 4，且由于 left = i ，造成无限循环 int i = (right + left + 1) / 2; int j = toall - i; if(nums1[i - 1] > nums2[j]){ right = i - 1; }else{ left = i; } } int i = (right + left + 1) / 2; int j = toall - i; // 左边的肯定要最大的 右边的要最小的 int leftNum1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]); int rightNum1 = (i == len1 ? Integer.MAX_VALUE : nums1[i]); int leftNum2 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]); int rightNum2 = (j == len2 ? Integer.MAX_VALUE : nums2[j]); if((len1 + len2) % 2 == 1){ return Math.max(leftNum1, leftNum2); }else{ return ((double)(Math.max(leftNum1, leftNum2) + Math.min(rightNum1, rightNum2))) / 2; } } }
