4.寻找两个有序数组的中位数

type

status

date

slug

summary

4. Median of Two Sorted Arrays

题目描述

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Example 2:

Constraints:

题解:

1.自己的解法

纯暴力解法，寻求两个有序数组的中位数即先把两个有序数组合并，并用algorithm库里的sort函数将新数组排序并输出中位数。

但这似乎是不太符合折腾的，采用归并排序试试。

首先回忆（重学）归并排序基础代码

然后运用此思想，将两个有序数组做最后一次合并

但似乎在时间复杂度上O(m+n)不符合要求

O(log(m+n)。看到 log，很明显，我们只有用到二分的方法才能达到，

还是得考虑边界问题和各式各样的递归啊