class Solution {
public:
int smallestDifference(vector<int>& a, vector<int>& b) {
}
};
面试题 16.06. 最小差
给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差
示例：
输入：{1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
输出：3，即数值对(11, 8)
提示：
1 <= a.length, b.length <= 100000-2147483648 <= a[i], b[i] <= 2147483647[0, 2147483647] 内原站题解
python3 解法, 执行用时: 284 ms, 内存消耗: 28.3 MB, 提交时间: 2022-11-30 11:27:36
class Solution:
def smallestDifference(self, a: List[int], b: List[int]) -> int:
a, b = [[i, 1] for i in a], [[i, 2] for i in b]
a = sorted(a+b)
return min([a[i+1][0] - a[i][0] if a[i+1][1] - a[i][1] != 0 else 2147483647 for i in range(len(a)-1)])
java 解法, 执行用时: 29 ms, 内存消耗: 49.3 MB, 提交时间: 2022-11-30 11:26:07
class Solution {
public int smallestDifference(int[] a, int[] b) {
Arrays.sort(b);
long res=2147483647;
for(int x:a)
{
int left=0;
int right=b.length-1;
int mid;
if(right==0)
{
res=Math.min(res,Math.abs(x-b[0]));
continue;
}
while(left<right)
{
mid=(left+right)/2;
res=Math.min(res,Math.abs((long)x-(long)b[mid]));
if(x>b[mid])
{
left=mid+1;
}
else right=mid;
}
}
return (int)res;
}
}
python3 解法, 执行用时: 144 ms, 内存消耗: 21.2 MB, 提交时间: 2022-11-30 11:24:43
class Solution:
def smallestDifference(self, a: List[int], b: List[int]) -> int:
m, n = len(a), len(b)
a.sort()
b.sort()
i = j = 0
diff = float('inf')
while i < m and j < n:
if a[i] == b[j]:
return 0
if diff > abs(a[i] - b[j]):
diff = abs(a[i] - b[j])
if a[i] < b[j]:
i += 1
else:
j += 1
return diff
java 解法, 执行用时: 21 ms, 内存消耗: 48.7 MB, 提交时间: 2022-11-30 11:16:02
class Solution {
public int smallestDifference(int[] a, int[] b) {
int m = a.length;
int n = b.length;
if (m == 1 && n == 1) {
return Math.abs(a[0] - b[0]);
}
Arrays.sort(a);
Arrays.sort(b);
int i = 0;
int j = 0;
long res = Long.MAX_VALUE;
while (i < m && j < n) {
if (a[i] == b[j]) {
return 0;
}
long dif = a[i] - b[j];
res = Math.min(Math.abs(dif), res);
if (dif > 0) {
j++;
} else {
i++;
}
}
return (int) res;
}
}