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 = 0
        res = float('inf')
        while i < len(a) and j < len(b):
            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 i = 0, j = 0;
        long res = Long.MAX_VALUE;
        while (i < a.length && j < b.length) {
            res = Math.min(res, Math.abs((long) a[i] - (long) b[j]));
            if (a[i] > b[j]) {
                ++j;
            } else {
                ++i;
            }
        }
        return (int) res;
    }
}

C++

class Solution {
public:
    int smallestDifference(vector<int>& a, vector<int>& b) {
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        int i = 0, j = 0;
        long res = LONG_MAX;
        while (i < a.size() && j < b.size()) {
            res = min(res, abs((long)a[i] - (long)b[j]));
            if (a[i] > b[j]) ++j;
            else ++i;
        }
        return res;
    }
};

Go

func smallestDifference(a []int, b []int) int {
	sort.Ints(a)
	sort.Ints(b)
	i, j, res := 0, 0, 2147483647
	for i < len(a) && j < len(b) {
		res = min(res, abs(a[i]-b[j]))
		if a[i] > b[j] {
			j++
		} else {
			i++
		}
	}
	return res
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

...