LeetCode 1385. 两个数组间的距离值

题目链接：

力扣https://leetcode-cn.com/problems/find-the-distance-value-between-two-arrays/

【分析】对于arr1中的任意一个arr1[i]来说如果arr2中离arr1[i]最近的两个元素和他的差值都比d大，那么其他元素必然也比d大，所以我们只需要对arr2排序，然后二分查找第一个比arr1[i]大的元素和第一个比arr1[i]小的元素即可。

class Solution {
    
    public int lowerBound(int[] arr, int target){
        int left = 0, right = arr.length - 1, mid;
        while(left <= right){
            mid = (left + right) >> 1;
            if(target < arr[mid]){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return right >= 0 && right < arr.length ? arr[right]: -10001;
    }

    public int upperBound(int[] arr, int target){
        int left = 0, right = arr.length - 1, mid;
        while(left <= right){
            mid = (left + right) >> 1;
            if(target <= arr[mid]){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return left >= 0 && left < arr.length ? arr[left] : 10001;
    }

    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int ans = 0;
        for(var i: arr1){
            if(Math.abs(lowerBound(arr2, i) - i) > d && Math.abs(upperBound(arr2, i) - i) > d) ans++;
        }
        return ans;
    }
}

【方法二】对上面的式子进行变形，要求|arr1[i]-arr2[j]|>d，如果查找到|arr1[i]-arr2[j]|<=d必然不符合要求，变形得arr1[i]-d<=arr2[j]<=arr1[i]+d，所以这里对arr2的二分可以稍微变形一下，查找到在这两个边界内的数就直接返回false即可。

class Solution {
    
    public boolean BinarySearch(int[] arr, int low, int high){
        int left = 0, right = arr.length - 1, mid;
        while(left <= right){
            mid = (left + right) >>> 1;
            if(arr[mid] >= low && arr[mid] <= high) return false;
            else if(arr[mid] < high) left = mid + 1;
            else right = mid - 1;
        }
        return true;
    }
    
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int low, high, ans = 0;
        for(var i: arr1){
            low = i - d; high = i + d;
            if(BinarySearch(arr2, low, high)) ans++;
        }
        return ans;
    }
}