Comment on page

4.Median-of-Two-Sorted-Arrays

4. 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. 1.
    A[k/2 - 1] <= B[k/2 - 1] => A和B合并后的第k大数中必包含A[0]~A[k/2 -1],可使用归并的思想去理解。
  2. 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);
}
}
​
}