Leetcode(4)|Leetcode(4) - 寻找两个有序数组的中位数 - java版 Leetcode(4)-寻找两个有序数组的

Leetcode(4) - 寻找两个有序数组的中位数 - java版题目
困难
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。

示例1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

示例2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

解题分析
先从题干进行分析 , 本题若没有时间复杂度要求,将是一道极简单的题.
我们可以先将两个数组合并,再排序 ,以此完成解题.
本题给出的时间复杂度为 O(log(m + n)) , 由此我们想到二分查找,事实也确乎如此.
下面开始分析问题,先从中位数的作用入手

中位数 : 将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。

对本题而言,我们要做的就是把有序数组A,B进行分割,共分为四个子数组,分别记作left_A,left_B,left_A,right_A.
将left_A和left_B合并记作left_part,
同理,得到right_part.

left_part	right_part
A[0], A[1], ..., A[i-1]	A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]	B[j], B[j+1], ..., B[n-1]

如果我们可以确认:

len(left_part) = len(right_part)

max(left_part) ≤ min(right_part)

那么,我们就得到了两个长度相同的部分,且其中一部分的元素总是大于或等于另一部分的元素.
到这里,我们就已经很接近答案了.
要满足上面的两个条件,我们只需要保证：

Leetcode(4)|Leetcode(4) - 寻找两个有序数组的中位数 - java版

文章图片
注意: 其中1中的 m - i + n - j + 1的 "+1"的原因是存由于在奇偶的差别.
从1中我们可以看出,j 可以被 i 表示,所以,接下来的问题变为:
找到满足2的 i
对此,我们可以使用二分查找(具体查找的过程,以及临界分析写在下面注释中)
当找到目标对象 i 后 , 中位数为 :

文章图片
【Leetcode(4)|Leetcode(4) - 寻找两个有序数组的中位数 - java版】
代码实现

class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; // 保证num1的长度总是小于或等于nums2 if(m>n){ int[] temp = nums1; nums1 = nums2; nums2 = temp; int lengthTemp = m; m = n; n = lengthTemp; } int imax = m,imin = 0,half = (m+n+1)/2 ; //开始查找 while(imax >= imin){ int i = (imax+imin)/2; int j = half - i; // i 过小且i可以再增大 if(inums1[i]){ imin = i +1; } // i 过大且i可以再减小 else if(i>imin && nums1[i-1]>nums2[j]){ imax = i -1; } else{ int leftmax = 0; // left_num1为空时 if(i == 0) {leftmax = nums2[j-1]; } // left_num2为空时 else if(j == 0){ leftmax = nums1[i-1]; } else {leftmax = Math.max(nums1[i-1],nums2[j-1]); } // 当m+n 为奇数时,返回奇数解 if((m+n)%2 == 1)return leftmax; int rightmin = 0; // right_num1为空时 if(i == m){ rightmin = nums2[j]; } // right_num2为空时 else if(j == n) {rightmin = nums1[i]; } else{ rightmin = Math.min(nums1[i],nums2[j]); } // 当m+n 为偶数时,返回偶数解 return (leftmax+rightmin)/2.0; } } return 0.0; } }

参考文章