请问有什么办法升级到38R?# PDA - 掌中宝
c*e
1 楼
给定两个排序数组A和B,找到A与B中元素最小差值。
如A={0,3}, B={2,7,9}, 结果是1(A中的3和B中的2的差值)
想到一个O(nlogn)的解法:取A中的每一个值,在B中进行binary search。贴个Java代
码如下。不知道有没有更好的解法。
public int minDiff(int[] a, int[] b) {
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i < a.length; i++) {
int n = a[i];
int low = 0;
int high = b.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (b[mid] == n)
return 0;
else if (b[mid] < n) {
minDiff = Math.min(minDiff, n - b[mid]);
low = mid + 1;
} else {
minDiff = Math.min(minDiff, b[mid] - n);
high = mid - 1;
}
}
}
return minDiff;
}
如A={0,3}, B={2,7,9}, 结果是1(A中的3和B中的2的差值)
想到一个O(nlogn)的解法:取A中的每一个值,在B中进行binary search。贴个Java代
码如下。不知道有没有更好的解法。
public int minDiff(int[] a, int[] b) {
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i < a.length; i++) {
int n = a[i];
int low = 0;
int high = b.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (b[mid] == n)
return 0;
else if (b[mid] < n) {
minDiff = Math.min(minDiff, n - b[mid]);
low = mid + 1;
} else {
minDiff = Math.min(minDiff, b[mid] - n);
high = mid - 1;
}
}
}
return minDiff;
}