面试题 16.06

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

1. megre sorted list O(nlog(n))

class Solution {
public:
    int smallestDifference(vector<int>& a, vector<int>& b) {
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        int n1 = a.size(), n2 = b.size();

        int i = 0, j = 0;
        long prev = LONG_MIN / 2, cur, res = LONG_MAX;
        bool previsa = true;
        while (i < n1 || j < n2) {
            bool curisa = true;
            if (i < n1 && (j >= n2 || a[i] < b[j]))
                cur = a[i++];
            else {
                cur = b[j++];
                curisa = false;
            }
            if (previsa != curisa)
                res = min(res, cur - prev);
            prev = cur;
            previsa = curisa;
        }

        return res;
    }
};

1. binary search O(nlog(n))

class Solution {
public:
    int smallestDifference(vector<int>& a, vector<int>& b) {
        sort(a.begin(), a.end());

        long res = LONG_MAX;
        for (long n : b) {
            auto it = lower_bound(a.begin(), a.end(), n);
            long diff1 = it != a.begin() ? n - *prev(it) : LONG_MAX; 
            long diff2 = it != a.end() ? *it - n : LONG_MAX; 
            res = min(res, min(diff1, diff2));
            if (res == 0) break;
        }

        return res;
    }
};