Smallest Difference: Given two arrays of integers, compute the pair of values (one value in each array) with the smallest (non-negative) difference. Return the difference.
EXAMPLE
1
2
|
Input: {1, 3, 15, 11, 2}, {23, 127,235, 19, 8}
Output: 3. That is, the pair (11, 8)
|
Hints: #632, #670, #679
解法1
把两个数组排序：
1
2
|
A: 1, 2, 3, 11, 15
B: 8, 19, 23, 127, 235
|
大家都先从先从第一个元素开始计算diff。
如果a < b，那么a得前进一步才有可能缩小diff。
如果b < a，那么b得前进一步才有可能缩小diff。
然后在过程中记录最小diff。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
int findSmallestDifference(int[] array1, int[] array2) {
Arrays.sort(array1);
Arrays.sort(array2);
int a = 0;
int b = 0;
int difference = Integer.MAX_VALUE;
while (a < array1.length && b < array2.length) {
if (Math.abs(array1[a] - array2[b]) < difference) {
difference = Math.abs(array1[a] - array2[b]);
}
/* Move smaller value. */
if (array1[a] < array2[b]) {
a++;
} else {
b++;
}
}
return difference;
}
|
时间复杂度：O(AlogA + BlogB + A + B) => O(AlogA + BlogB)，A和B是两个数组的长度。
评论