Finley.Hamilton 发表于3年前

• 发表于 3年前
• 阅读 1171
• 收藏 3
• 评论 0

# 题目

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)).

# 思路

1. 丢掉一个最小的，丢掉一个最大的
2. 如果剩下小于等于两个数字，可以从中得到中位数
3. 标准写法不是这样的，是通过寻找第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;
}
}
``````

Finley.Hamilton

×