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

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

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]

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);
    }
  }

}