samprasyork
BAN USERpublic int getMin(int[] mouse, int[] holes) {
if (mouse == null || holes == null) {
return -1;
}
int lenM = mouse.length;
int lenH = holes.length;
if (lenM == 0 || lenH == 0 || lenM > lenH) {
return -1;
}
int result = 0;
int[] position = new int[lenM];
for (int i = 0; i < lenM; i++) {
position[i] = i;
}
for (int i = lenM; i < lenH; i++) {
if (!adjust(mouse, holes, position, i, lenM - 1)) {
break;
}
}
for (int i = 0; i < lenM; i++) {
result = Math.max(result, Math.abs(mouse[i] - holes[position[i]]));
}
return result;
}
private boolean adjust(int[] mouse, int[] holes, int[] position,
int holeIndex, int lastMouse) {
if (lastMouse < 0) {
return false;
}
if (Math.abs(mouse[lastMouse] - holes[position[lastMouse]]) > Math
.abs(mouse[lastMouse] - holes[holeIndex])) {
position[lastMouse] = holeIndex;
adjust(mouse, holes, position, holeIndex - 1, lastMouse - 1);
return true;
}
return false;
}
Yes, this is the correct answer. But we can optimize it. if |holes| - |mice| = 1,
and if mn stick to hn, but not hn+1, mn-i would stick to the original one
DP can solve it.
- samprasyork October 23, 2014public int min2(int[] mouse, int[] holes) {
if (mouse == null || holes == null)
return -1;
int lenM = mouse.length;
int lenH = holes.length;
if (lenM > lenH)
return -1;
Arrays.sort(mouse);
Arrays.sort(holes);
int[][] DP = new int[lenM][lenH];
DP[0][0] = Math.abs(mouse[0] - holes[0]);
int min = DP[0][0];
for (int i = 0; i < lenH; i++) {
DP[0][i] = min = Math.min(min, Math.abs(mouse[0] - holes[i]));
}
for (int i = 1; i < lenM; i++) {
DP[i][i] = Math.max(DP[i - 1][i - 1], Math.abs(mouse[i] - holes[i]));
}
for (int i = 1; i < lenM; i++) {
for (int j = i + 1; j < lenH; j++) {
DP[i][j] = Math.min(DP[i][j - 1],
Math.max(DP[i - 1][j - 1], Math.abs(mouse[i] - holes[j])));
}
}
return DP[lenM - 1][lenH - 1];
}