guanxiaohua
BAN USERThe previous Java code doesn't work in the case that one of the Array will run out earlier. Here is the modified one:
public class Median {
public static void main(String args[]) {
int a[] = { 0, 1, 2, 3 ,4 ,5,7,8,9};
int b[] = { 0, 1, 4, 6, 7, 8, 9, 11, 12};
System.out.print("a[]:");
for(int i:a)
{
System.out.print(" "+i);
}
System.out.print("\nb[]:");
for(int i:b)
{
System.out.print(" "+i);
}
System.out.print("\nMedian: ");
findMedian(a, b);
}
/*
* Two sorted arrays as input, we need to asssume that the two arrays are of the same length
*/
public static void findMedian(int a[], int b[]) {
int totalLength = a.length + b.length;
int median1 = 0;
int median2 = 0;
if (totalLength % 2 == 0) {
median1 = totalLength / 2;
median2 = median1 - 1;
System.out.println("Two medians");
} else {
median1 = totalLength / 2;
median2 = -1;
System.out.println("One median");
}
int aPtr = 0;
int bPtr = 0;
int previousMove = -1;
int recentMove = -1;
boolean aOver=false; //one of the array could run out earlier
boolean bOver=false;
while ( aPtr + bPtr < median1 ) {
if ((!aOver&&!bOver))
{
if(a[aPtr] < b[bPtr])
{
aPtr++; previousMove = recentMove; recentMove = 0;
if(aPtr==a.length)
aOver=true;
}
else
{
bPtr++; previousMove = recentMove; recentMove = 1;
if(bPtr==b.length)
bOver=true;
}
continue;
}
//now some one is Over.
if (bOver) {
aPtr++; previousMove = recentMove; recentMove = 0;
if(aPtr==a.length)
aOver=true;
}
else{//aOver
bPtr++; previousMove = recentMove; recentMove = 1;
if(bPtr==b.length)
bOver=true;
}
//System.out.println(" recentMove:"+recentMove+" a[aPtr]="+(aOver?"over":a[aPtr])+" b[bPtr]="+(bOver?"over":b[bPtr]));
}//end while
//now that aPtr+bPtr==median1, means that before there two ponters, lie half of the total numbers
System.out.print("\nMedian:");
//if (recentMove == 0) {
//if(a[aPtr]<=b[bPtr]){
//judge if any of the array has run out
if(bOver){
System.out.print(a[aPtr]);
} else if(aOver) {
System.out.print(b[bPtr]);
}
else //neither of the arrays run over
{
if(a[aPtr]<=b[bPtr]){
System.out.print(a[aPtr]);
} else {
System.out.print(b[bPtr]);
}
}
if (median2 != -1) {
if(previousMove==0)
System.out.println(" and " + a[aPtr-1]);
else
System.out.println(" and " + b[bPtr-1]);
}
}
}
I tested the InOrder algo, seems at least some bug here:
3 3
1 2 5
2 3 6
3 4 7
InOrder:
1 2 2 2 3 3 3 4 5 6 7
the last paragraph is messy, simplify here:
- guanxiaohua March 16, 2011if (median2 != -1) {
if(previousMove==0)
System.out.println(" and " + a[aPtr-1]);
else
System.out.println(" and " + b[bPtr-1]);
}