Leetcode刷题---1385

题目：给你两个整数数组 arr1 ，arr2 和一个整数 d ，请你返回两个数组之间的距离值。[距离值] 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i] - arr2[j] <= d 。

输入：arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2

输出：2

class Solution {
public:
    int findTheDistanceValue(vector& arr1, vector& arr2, int d) {
        int cnt = 0;
        for (auto &x: arr1) {
            bool ok = true;
            for (auto &y: arr2) {
                ok &= (abs(x - y) > d);
            }
            cnt += ok;
        }
        return cnt;
    }
};

复杂度分析

时间复杂度：O(n x m)

空间复杂度：O(1)

class Solution {
public:
    int findTheDistanceValue(vector& arr1, vector& arr2, int d) {
        sort(arr2.begin(), arr2.end());
        int cnt = 0;
        for (auto &x: arr1) {
            unsigned p = lower_bound(arr2.begin(), arr2.end(), x) - arr2.begin();
            bool ok = true;
            if (p < arr2.size()) {
                ok &= (arr2[p] - x > d);
            }
            if (p - 1 >= 0 && p - 1 <= arr2.size()) {
                ok &= (x - arr2[p - 1] > d);
            }
            cnt += ok;
        }
        return cnt;
    }
};

复杂度分析

时间复杂度：O(nlogm)

空间复杂度：O(1)