README_EN.md

16.06. Smallest Difference

中文文档

Description

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:

Input: {1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}

Output:  3, the pair (11, 8)

Note:

• 1 <= a.length, b.length <= 100000
• -2147483648 <= a[i], b[i] <= 2147483647
• The result is in the range [-2147483648, 2147483647]

Solutions

Python3

class Solution:
    def smallestDifference(self, a: List[int], b: List[int]) -> int:
        a.sort()
        b.sort()
        i, j, res = 0, 0, 2147483647
        m, n = len(a), len(b)
        while i < m and j < n:
            if a[i] == b[j]: return 0
            res = min(res, abs(a[i] - b[j]))
            if a[i] > b[j]: j += 1
            else: i += 1
        return res
        

Java

class Solution {
    public int smallestDifference(int[] a, int[] b) {
        Arrays.sort(a);
        Arrays.sort(b);
        int m = a.length, n = b.length;
        int i = 0, j = 0;
        long res = Long.MAX_VALUE;
        while (i < m && j < n) {
            if (a[i] == b[j]) return 0;
            res = Math.min(res, Math.abs((long) a[i] - (long) b[j]));
            if (a[i] > b[j]) ++j;
            else ++i;
        }
        return (int) res;
    }
}

...