Leetcode skimming ---1385

subject ： Here are two arrays of integers  arr1 ,arr2  And an integer  d , Please return the distance between two arrays .[ Distance value ] Number of elements defined as meeting this distance requirement ： For elements  arr1[i] , There are no elements  arr2[j]  Satisfy |arr1[i] - arr2[j] <= d .

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

Output ：2

Direction one ： simulation

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& 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;
    }
};

Complexity analysis

Time complexity ：O(n x m)

Spatial complexity ：O(1)

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& 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;
    }
};

Complexity analysis

Time complexity ：O(nlogm)

Spatial complexity ：O(1)