题目
给定两个大小分别为 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
解法一
先将两个数组合并，两个有序数组的合并也是归并排序中的一部分。然后根据奇数，还是偶数，返回中位数。
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] result=new int[nums1.length+nums2.length];
int i=0;// 数组一下标
int j=0;// 数组二下标
int k=0;// 数组三下标
while (i<nums1.length&&j<nums2.length){
if (nums1[i]<nums2[j]){
result[k++]=nums1[i++];
}else {
result[k++]=nums2[j++];
}
}
while (i<nums1.length){
result[k++]=nums1[i++];
}
while (j<nums2.length){
result[k++]=nums2[j++];
}
int length = result.length;
double median=0.0;
if (length%2>0){
// 说明是奇数长度的
median=result[length/2];
}else {
median=(result[length/2]+result[(length/2)-1])/2.0;
}
return median;
}
}解法二
不需要将两个数组真的合并，只需要找到中位数在哪里就可以
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int length = nums1.length+nums2.length;
int left =0;
int right =0;
int i=0;// 数组一下标
int j=0;// 数组二下标
for (int l = 0; l <= length / 2; l++) {
left=right;
if (i<nums1.length&&(j>=nums2.length||nums1[i]<nums2[j])){
right=nums1[i++];
}else {
right=nums2[j++];
}
}
if (length%2>0){
return right;
}else {
return (right+left)/2.0;
}
}
}