问题描述
给定两个大小为m和n的有序数组nums1和nums2，找出这两个有序数组的中位数。
示例一：
nums1=[1,3]
nums2=[2]
则中位数为2
示例二：
nums1=[1，2]
nums2=[3，4]
则中位数为（2+3）/ 2 = 2.5
示例三：
nums1 = [1,3,6,8]
nums2 = [2,4,7,9,10,15]
输出结果为6.5
解决方案
当两个有序数组的长度之和为奇数的时候，中位数只有一个。
当两个有序数组的长度之和为偶数的时候，则中位数为数组合并之后位于中间的两个数的平均数。
这里我们使用二分查找求取中位数
1.如果两个有序数组的长度之和为偶数，则我们划分左边元素个数和右边元素个数是相等的。
2.如果两个有序数组的长度之和为奇数，则我们划分左边元素个数比右边元素个数多一个。（同理：右边比左边多一个也是可以的）
3.一个必须满足的条件：分隔线左边所有元素的数值<=分隔线右边所有元素数值。
这样一来，左边最大的那个值就是两个有序数组合并之后的中位数了。
同样情况，当两个有序数组的长度之和为偶数时，我们划分两边元数个数相等，当然，左边所有元素数值<=右边所有元素数值。
package Solutions; public class Solution { public double findMedianSortedArrays(){ int[] nums1 = {1,3,6,8}; int[] nums2 = {2,4,7,9,10,15}; //为了使得分隔线在第二个数组的两侧都有元素，以至于不会出现访问时下标越界的情况 if (nums1.length>nums2.length){ //如果第一个数组长度大于第二个数组的长度 //则将较短的那个数组设置成第一个数组 int[] nums3 = nums1; nums1 = nums2; nums2 = nums3; } int m = nums1.length; int n = nums2.length; //分隔线左边的所有元素个数需要满足的个数 (m+n+1)/2 int totalLeft = (m+n+1)/2; //在nums1的区间[0，m]里查找恰当的分割线， //使得nums1[i-1] <= nums2[j] &&nums[j-1] <= nums1[i] int left = 0; int right = m; while (left<right){ int i = left+(right-left+1)/2; int j = totalLeft-i; if (nums1[i-1]>nums2[j]){ //下一轮搜索的区间[left,i-1] right = i-1; }else { //下一轮搜索的区间是[i,right] left = i; } } int i = left; int j = totalLeft-i; int nums1LeftMax = i == 0? Integer.MIN_VALUE : nums1[i-1]; int nums1RightMin = i == m? Integer.MAX_VALUE :nums1[i]; int nums2LeftMax = j == 0? Integer.MIN_VALUE : nums2[j-1]; int nums2RightMin = j == m? Integer.MAX_VALUE :nums2[j]; if ((m+n)%2==1){ return Math.max(nums1LeftMax,nums2LeftMax); }else { double a= (double) (Math.max(nums1LeftMax,nums2LeftMax)+Math.min(nums1RightMin,nums2RightMin))/2; System.out.println(a); return a; } } public static void main(String[] args) { Solution solution = new Solution(); solution.findMedianSortedArrays( ); } } |
结语
本文章简要介绍使用二分查找方法解决两个有序数组的中位数，解决这个问题还可以使用先将两个数组进行合并，然后再求取中位数。
