README.md

面试题 16.06. 最小差

English Version

题目描述

给定两个整数数组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
• 正确结果在区间[-2147483648, 2147483647]内

解法

Python3

class Solution:
    def smallestDifference(self, a: List[int], b: List[int]) -> int:
        a.sort()
        b.sort()
        i = j = 0
        res = 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
}

...