力扣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;}};
