最小差

题意

给定两个整数数组(第一个是数组 A,第二个是数组 B),在数组 A 中取 A[i],数组 B 中取 B[j],A[i] 和 B[j]两者的差越小越好(|A[i] - B[j]|)。返回最小差。

样例

给定数组 A = [3,4,6,7], B = [2,3,8,9],返回 0

思路

首先对两个数组进行排序,然后设 2 个指针 i, j 分别指向 A 和 B 的第一个元素,依次向后遍历,取 A[i] - A[j] 的绝对值,就是差值,将遍历过程中最小的差值记录下来,若遍历过程中 A[i] == A[j] ,那么就直接返回 0。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
/**
* @param A, B: Two integer arrays.
* @return: Their smallest difference.
*/
public int smallestDifference(int[] A, int[] B) {
if (A == null || A.length == 0 || B == null || B.length == 0) {
return 0;
}

Arrays.sort(A);
Arrays.sort(B);

int i = 0;
int j = 0;
int min = Integer.MAX_VALUE;
while (i < A.length && j < B.length) {
min = Math.min(min, Math.abs(A[i] - B[j]));
if (A[i] > B[j]) {
j++;
} else if (A[i] < B[j]) {
i++;
} else {
return 0;
}
}
return min;
}
}

原题地址

LintCode:最小差