# 4.Median-of-Two-Sorted-Arrays

## 4. Median of Two Sorted Arrays

## 题目地址

<https://leetcode.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
```

## 代码

### Approach 1: Merge sort with equal length

```java
class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
    if ((A == null || A.length == 0) && (B == null || B.length == 0)) {
      return -1.0;
    }

    int lenA = (A == null) ? 0 : A.length;
    int lenB = (B == null) ? 0 : B.length;
    int len = lenA + lenB;

    int indexA = 0, indexB = 0, indexC = 0;
    int[] C = new int[len];
    while (indexA < lenA && indexB < lenB) {
      if (A[indexA] < B[indexB]) {
        C[indexC++] = A[indexA++];
      } else {
        C[indexC++] = B[indexB++];
      }
    }

    while (indexA < lenA) {
      C[indexC++] = A[indexA++];
    }

    while (indexB < lenB) {
      C[indexC++] = B[indexB++];
    }

    int indexM1 = (len - 1) / 2;
    int indexM2 = len / 2;
    if (len % 2 == 0) {
      return (C[indexM1] + C[indexM2]) / 2.0;
    } else {
      return C[indexM2];
    }

  }
}
```

### Approach #2 space optimization

```java
class Solution {
    /**
     * @param A: An integer array.
     * @param B: An integer array.
     * @return: a double whose format is *.5 or *.0
     */
    public double findMedianSortedArrays(int[] A, int[] B) {
        if ((A == null || A.length == 0) && (B == null || B.length == 0)) {
            return -1.0;
        }
        int lenA = (A == null) ? 0 : A.length;
        int lenB = (B == null) ? 0 : B.length;
        int len = lenA + lenB;
        int m1 = 0, m2 = 0;

        /* merge sort */
        int indexA = 0, indexB = 0, indexC = 0;
        // case1: both A and B have elements
        while (indexA < lenA && indexB < lenB) {
            if (indexC > len / 2) {
                break;
            }
            if (indexC == (len - 1) / 2) {
                m1 = Math.min(A[indexA], B[indexB]);
            }
            if (indexC == len / 2) {
                m2 = Math.min(A[indexA], B[indexB]);
            }

            if (A[indexA] < B[indexB]) {
                indexA++;
            } else {
                indexB++;
            }
            indexC++;
        }
        // case2: only A has elements
        while (indexA < lenA) {
            if (indexC > len / 2) {
                break;
            }
            if (indexC == (len - 1) / 2) {
                m1 = A[indexA];
            }
            if (indexC == len / 2) {
                m2 = A[indexA];
            }
            indexA++;
            indexC++;
        }
        // case3: only B has elements
        while (indexB < lenB) {
            if (indexC > len / 2) {
                break;
            }
            if (indexC == (len - 1) / 2) {
                m1 = B[indexB];
            }
            if (indexC == len / 2) {
                m2 = B[indexB];
            }
            indexB++;
            indexC++;
        }

        // return median for even and odd cases
        if (len % 2 == 0) {
            return (m1 + m2) / 2.0;
        } else {
            return m2;
        }
    }
}
```

### Approach #3 归并排序

题中已有信息两个数组均为有序，找中位数的关键在于找到第一半大的数，显然可以使用二分搜索优化。本题是找中位数，其实可以泛化为一般的找第 k 大数，这个辅助方法的实现非常有意义！在两个数组中找第k大数->找中位数即为找第k大数的一个特殊情况——第(A.length + B.length) / 2 大数。因此首先需要解决找第k大数的问题。这个联想确实有点牵强...

由于是找第k大数(从1开始)，使用二分法则需要比较A\[k/2 - 1]和B\[k/2 - 1]，并思考这两个元素和第k大元素的关系。

1. A\[k/2 - 1] <= B\[k/2 - 1] => A和B合并后的第k大数中必包含A\[0]\~A\[k/2 -1]，可使用归并的思想去理解。
2. 若k/2 - 1超出A的长度，则必取B\[0]\~B\[k/2 - 1]

```java
class Solution {
  public double findMedianSortedArrays(int[] A, int[] B) {
    if ((A == null || A.length == 0) && (B == null || B.length == 0)) return -1.0;

    int lenA = (A == null) ? 0 : A.length;
    int lenB = (B == null) ? 0 : B.length;
    int len = lenA + lenB;

    if (len % 2 == 0) {
      return (findKth(A, 0, B, 0, len / 2) + findKth(A, 0, B, 0, len / 2 + 1)) / 2.0;
    } else {
      return findKth(A, 0, B, 0, len / 2 + 1);
    }
  }

  private int findKth(int[] A, int indexA, int[] B, int indexB, int k) {
    // left
    int lenA = (A == null) ? 0 : A.length;
    if (indexA > lenA - 1) {
      return B[indexB + k - 1];
    }
    // right
    int lenB = (B == null) ? 0 : B.length;
    if (indexB > lenB - 1) {
      return A[indexA + k - 1];
    }
        // only one 
    if (k == 1) return Math.min(A[indexA], B[indexB]);

    // binary search  k / 2 - 1
    int keyA = Integer.MAX_VALUE, keyB = Integer.MAX_VALUE;
    if (indexA + k / 2 - 1 < lenA) keyA = A[indexA + k / 2 - 1];
    if (indexB + k / 2 - 1 < lenB) keyB = B[indexB + k / 2 - 1];
        // Compare the two values
    if (keyA > keyB) {
      return findKth(A, indexA, B, indexB + k / 2, k - k / 2);
    } else {
      return findKth(A, indexA + k / 2, B, indexB, k - k / 2);
    }
  }

}
```


---

# 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://wentao-shao.gitbook.io/leetcode/array/4.median-of-two-sorted-arrays.md?ask=<question>
```

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.