# 4. Median of Two Sorted Arrays

## 刷题内容

• https://leetcode-cn.com/problems/median-of-two-sorted-arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5



## 解题方案

class Solution {
// 寻找两个有序数组的中位数
// 问题转换为求第K大的数
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if(nums1 == null || nums1.length == 0){
// 求nums2的中位数
return nums2.length % 2 == 0 ? (nums2[nums2.length / 2] + nums2[nums2.length / 2 - 1]) / 2.0 : nums2[nums2.length / 2];
}
if(nums2 == null || nums2.length == 0){
return nums1.length % 2 == 0 ? (nums1[nums1.length / 2] + nums1[nums1.length / 2 - 1]) / 2.0 : nums1[nums1.length / 2];
}
int len = nums1.length + nums2.length;
return len % 2 == 0 ? (topK(nums1,nums2,0,0,len/2)+topK(nums1,nums2,0,0,len/2+1))/2.0 : topK(nums1,nums2,0,0,len/2 + 1);
}
// 找两个有序数组的topk小的数
public int topK(int[] nums1,int[] nums2,int start1,int start2,int k){
if(start1 >= nums1.length){
return nums2[start2 + k - 1];
}
if(start2 >= nums2.length){
return nums1[start1 + k - 1];
}

if(k == 1){
return Math.min(nums1[start1] , nums2[start2]);
}

if(start1 + k / 2 > nums1.length){ // 肯定不会在nums2的前 k / 2
}else if(start2 + k / 2 > nums2.length){
}

int mid1 = nums1[start1 + k / 2 - 1];
int mid2 = nums2[start2 + k / 2 - 1];
if(mid1 > mid2){ // 移除nums2的前k/2