65. Median of two sorted arrays

Leave a comment

August 20, 2016 by oneOokay

method1. merge two sorted array until you get the median

public double findMedianSortedArrays(int[] A, int[] B) {
int length = A.length + B.length;
int[] merged = new int[length / 2 + 1];
int index = 0;
int i = 0;
int j = 0;
while(index < merged.length){
if(i < A.length && j < B.length)
{
if(A[i] < B[j]){ merged[index] = A[i]; i ++; }else { merged[index] = B[j]; j ++; } }else if (i >= A.length){
merged[index] = B[j];
j ++;
}else{
merged[index] = A[i];
i ++;
}
index ++;
}

if(length % 2 == 0) {
return (merged[length / 2 - 1] + merged[length / 2] ) / 2.0;
}
else {
return merged[length / 2];
}
}

method2. findKth

  1. “扔掉”A或B的前k/2个数
public double findMedianSortedArrays(int[] A, int[] B) {
int length = A.length + B.length;
if (length % 2 == 0) {
return (findKth(A, 0, B, 0, length / 2) + findKth(A, 0, B, 0, length / 2 + 1)) / 2.0;
}
else {
return findKth(A, 0, B, 0, length / 2 + 1);
}
}

public double findKth(int[] A, int a_start, int[] B, int b_start, int k) {
if (a_start >= A.length){
return B[b_start + k - 1];
}

if (b_start >= B.length){
return A[a_start + k - 1];
}

//find the first smaller element in two sorted array.
if (k == 1){
return Math.min(A[a_start], B[b_start]);
}

//如果A长度不够,就“扔”B,所以a_key = Integer.MAX_VALUE
int a_key = a_start + k / 2 - 1 < A.length? A[a_start + k / 2 - 1] : Integer.MAX_VALUE;
//如果B长度不够,就“扔”A,所以b_key = Integer.MAX_VALUE
int b_key = b_start + k / 2 - 1 < B.length? B[b_start + k / 2 - 1] : Integer.MAX_VALUE;

//当a_key的值比b_key的值小的时候,“扔”A;反之“扔”B
if (a_key < b_key) {
return findKth(A, a_start + k / 2, B, b_start, k - k / 2); //不能直接写k/2
}else {
return findKth(A, a_start, B, b_start + k / 2, k - k / 2);
}

}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: