leichongchong
BAN USERthis algorithm is good, but needs a global variable to hold the prev node value if using recursion.
- leichongchong October 06, 2012public static int[] MinimumDifference(int[] X, int[] Y, int[] Z) {
int[] resultAndIndex={Integer.MAX_VALUE,-1,-1,-1};
int xIndex=0;
int yIndex=0;
int zIndex=0;
while (resultAndIndex[0] > 0 && xIndex < X.length && yIndex < Y.length && zIndex < Z.length){
//find the maximum number and the minimum number
int max = X[xIndex];
int min = X[xIndex];
boolean xIsMin = true;
boolean yIsMin = false;
if (Y[yIndex] > max){max=Y[yIndex];}
else if (Y[yIndex] < min) {min=Y[yIndex]; xIsMin = false; yIsMin = true;}
if (Z[zIndex] > max) {max = Z[zIndex];}
else if (Z[zIndex] < min) {min = Z[zIndex]; xIsMin = false; yIsMin = false;}
//store the minimum result up to now
if (resultAndIndex[0] > max - min){
resultAndIndex[0] = max - min; //the minimum difference
resultAndIndex[1] = xIndex; //1 is for xIndex
resultAndIndex[2] = yIndex; //2 is for yIndex
resultAndIndex[3] = zIndex; //3 is for zIndex
}
if (xIsMin) xIndex++;
else if (yIsMin) yIndex++;
else zIndex++;
}
return resultAndIndex;
}
There is a bug in the code. When comparing n.data with p and q, we should use ">=" and "<=" instead of ">" & "<". Other wise, the BST like below is returned false.
- leichongchong October 06, 2012