Finley.Hamilton

# 题目

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

2016/12/06
12
0
Median of Two Sorted Arrays

①原题 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)). ②乡村......

2014/08/18
0
4

oschina
2017/09/28
3.3K
3

2017/12/19
0
0

m2012
2012/05/19
0
1

Guava RateLimiter + AOP注解实现单机限流、统计QPS

1、基于springboot项目pom.xml添加如下依赖： <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-aop</artifactId></dependency><d......

18分钟前
3
0

gugudu
23分钟前
2
0
BI报表分析和数据可视化，推荐这三个开源工具！

30分钟前
1
0
CountDownLatch

CountDownLatch的概念 CountDownLatch是一个同步工具类，用来协调多个线程之间的同步，或者说起到线程之间的通信（而不是用作互斥的作用）。 CountDownLatch能够使一个线程在等待另外一些线程...

39分钟前
1
0
centos7 新手阿里云服务器安装mongodb

49分钟前
3
0