# Median of Two Sorted Arrays
## 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.
### 例子
> Input: nums1 = \[1,3], nums2 = \[2]
>
> Output: 2.00000
>
> Explanation: merged array = \[1,2,3] and median is 2.
>
> Input: nums1 = \[1,2], nums2 = \[3,4]
>
> Output: 2.50000
>
> Explanation: merged array = \[1,2,3,4] and median is (2 + 3) / 2 = 2.5.
>
> Input: nums1 = \[0,0], nums2 = \[0,0]
>
> Output: 0.00000
>
> Input: nums1 = \[], nums2 = \[1]
>
> Output: 1.00000
**Follow up:**
The overall run time complexity should be `O(log (m+n))`.
**Constrain：**
> * `nums1.length == m`
> * `nums2.length == n`
> * `0 <= m <= 1000`
> * `0 <= n <= 1000`
> * `1 <= m + n <= 2000`
> * `-106 <= nums1[i], nums2[i] <= 106`
### 解法一
O(m+n)的解法比较直观，直接merge两个数组，然后找到第k大的元素（题中及寻找中位数） 但是merge之后，如果使用“排序”的操作，时间花费是expensive的。
也可以用一个计数器，记录当前已经找到第m大的元素，同时再使用两个指针pA和pB，分别指向A和B数组的第一个元素，使用merge sort的原理：
如果数组A当前元素小，则pA++，同时m++；
如果数组B当前元素小，则pB++，同时m++。
最终当m等于k的时候，及得到答案，时间复杂度：O（K），空间复杂度O（1） 如果当K很接近m+n的时候，这个方法还是O（m+n）的。
```cpp
class Solution {
public:
double findMedianSortedArrays(vector& A, vector& B) {
int m = A.size();
int n = B.size();
if(m > n){
vector temp;
temp.assign(A.begin(),A.end());
A.assign(B.begin(),B.end());
B.assign(temp.begin(),temp.end());
int tmp = m; m = n; n = tmp;
}
int imin = 0, imax = m, halflen = (m+n+1)/2;
while(imin <= imax){
int i = (imin+imax)/2;
int j = halflen-i;
if(i < imax && B[j-1]>A[i]){
imin = i + 1; // i is too small
}
else if(i > imin && A[i-1] > B[j]){
imax = i - 1; // i is too big
}else{
int maxleft = 0;
if(i == 0){maxleft = B[j-1];}
else if(j == 0){maxleft = A[i-1];}
else {maxleft = max(A[i-1], B[j-1]);}
if((m + n) % 2 == 1){return maxleft;}
int minright = 0;
if(i == m){minright = B[j];}
else if(j == n){minright = A[i];}
else {minright = min(A[i], B[j]);}
return (maxleft + minright) / 2.0;
}
}
return 0.0;
}
};
```
### 解法二
递归的方法：
```cpp
class Solution {
public:
double findMedianSortedArrays(const vector& A, const vector& B) {
const int m = A.size();
const int n = B.size();
int total = m + n;
if (total & 0x1)
return find_kth(A.begin(), m, B.begin(), n, total / 2 + 1);
else
return (find_kth(A.begin(), m, B.begin(), n, total / 2) + find_kth(A.begin(), m, B.begin(), n, total / 2 + 1)) / 2.0;
}
private:
static int find_kth(std::vector::const_iterator A, int m, std::vector::const_iterator B, int n, int k) {
//always assume that m is equal or smaller than n
if (m > n) return find_kth(B, n, A, m, k);
if (m == 0) return *(B + k - 1);
if (k == 1) return min(*A, *B);
//divide k into two parts
int ia = min(k / 2, m), ib = k - ia;
if (*(A + ia - 1) < *(B + ib - 1))
return find_kth(A + ia, m - ia, B, n, k - ia);
else if (*(A + ia - 1) > *(B + ib - 1))
return find_kth(A, m, B + ib, n - ib, k - ib);
else
return A[ia - 1];
}
};
```
## 总结
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://celia-qian.gitbook.io/leetcode-notebook-2020-2021/linear-list/array/median-of-two-sorted-arrays.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.