力扣1385.两个数组间的距离值

力扣1385.两个数组间的距离值

• 二分判断答案是否正确

•   class Solution {
    public:
        int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
            ranges::sort(arr2);
            ranges::sort(arr1);
            int m = arr2.size();
            auto check = [&](int low,int high) -> bool
            {
                int l = 0,r = m - 1;
                //等于也得判一下
                while(l <= r)
                {
                    int mid = l + r >> 1;
                    if(arr2[mid] <= high && arr2[mid] >= low) return true;
                    else if(arr2[mid] < low) l = mid + 1;
                    else if(arr2[mid] > high) r = mid - 1;
                }
                return false;
            };
            int res=0;
            for(auto v:arr1)
            {
                //看arr2中有没有元素使在[low,high]内的
                int low = v - d;
                int high = v + d;
                if(!check(low,high)) res++;
            }
            return res;
        }
    };