题目
There are two sorted arrays A and B 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)).
思路
- 丢掉一个最小的，丢掉一个最大的
- 如果剩下小于等于两个数字，可以从中得到中位数
- 标准写法不是这样的，是通过寻找第K小的数来实现的
该方法的核心是将原问题转变成一个寻找第k小数的问题（假设两个原序列升序排列），这样中位数实际上是第(m+n)/2小的数。所以只要解决了第k小数的问题，原问题也得以解决。 首先假设数组A和B的元素个数都大于k/2，我们比较A[k/2-1]和B[k/2-1]两个元素，这两个元素分别表示A的第k/2小的元素和B的第k/2小的元素。这两个元素比较共有三种情况：>、<和=。如果A[k/2-1]<B[k/2-1]，这表示A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
#代码
public class Solution { public double findMedianSortedArrays(int A[], int B[]) { int aMinIndex = 0; int aMaxIndex = A.length - 1; int bMinIndex = 0; int bMaxIndex = B.length - 1; while (aMaxIndex - aMinIndex + 1 + (bMaxIndex - bMinIndex + 1) > 2) { boolean minInA = true; boolean maxInA = true; // drop the minimum one if (aMaxIndex >= aMinIndex && bMaxIndex >= bMinIndex) { minInA = A[aMinIndex] < B[bMinIndex]; } else if ( bMaxIndex >= bMinIndex ) { minInA = false; } int useless = minInA?aMinIndex++:bMinIndex++; // drop the maximum one if (aMaxIndex >= aMinIndex && bMaxIndex >= bMinIndex) { maxInA = A[aMaxIndex] > B[bMaxIndex]; } else if ( bMaxIndex >= bMinIndex ) { maxInA = false; } useless = maxInA?aMaxIndex--:bMaxIndex--; } //System.out.println(A[aMinIndex] + " " + A[aMaxIndex]); //System.out.println(B[bMinIndex] + " " + A[bMaxIndex]); if (aMaxIndex == aMinIndex && bMaxIndex == bMinIndex) { return (A[aMaxIndex] + B[bMaxIndex]) * 1.0 / 2; } else if (aMaxIndex == aMinIndex){ return A[aMaxIndex]; } else if (bMaxIndex == bMinIndex) { return B[bMaxIndex]; } else if (aMaxIndex - aMinIndex == 1) { return (A[aMinIndex] + A[aMaxIndex]) * 1.0 / 2; } else if (bMaxIndex - bMinIndex == 1) { return (B[bMinIndex] + B[bMaxIndex]) * 1.0 / 2; } return -1; }} 