二分-数学推导区间-两个数组的距离值leetcode-1385
目录
（二分 数学推导区间 两个数组的距离值）leetcode 1385
数学推导：
设arr1[i]=x 则|x-arr2[j]|<=d
也就是当arr2[j]属于[x-d,x+d]的范围的时候，就不满足条件
执行过程：
我们把arr2排序
使用lower_bound找到第一个大于等于x-d的数为t
再判断是否位于end()或者*t>x+d
而这个数t有三种可能
1.刚好等于x-d不满足条件
2.大于x-d但是小于等于x+d 不满足条件
3.大于x+d 满足条件
那arr2中小于t的值呢，因为t>=x-d 所以arr2<t的值一定arr[j]<x-d满足区间条件
为什么不选upper_bound?
答：当x-d存在于arr2 但是t不等于x-2导致判断出错
class Solution {
public:
int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
sort(arr2.begin(),arr2.end());
int ans=0;
for(auto x:arr1)
{
auto t=ranges::lower_bound(arr2,x-d);
if(t==arr2.end()||*t>x+d)
ans++;
}
return ans;
}
};