中信建设内部网站搜索网页

题目：

给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。

「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。

思路：对于 arr1​ 中的元素 x，如果 arr2​ 没有在 [x−d,x+d] 中的数，那么答案加一。

方法：把 arr2从小到大排序，这样我们可以二分查找。遍历 arr1，设 x=arr1[i]，在 arr2中二分查找 ≥x−d 的最小的数 y。如果 y 不存在，或者 y>x+d，那么说明 arr2没有在 [x−d,x+d] 中的数，答案加一。

代码：

class Solution {public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {Arrays.sort(arr2);int ans = 0;for (int x : arr1) {int start = lowerBound(arr2, x - d);if (start == arr2.length || arr2[start] > x + d) {ans++;}}return ans;}private int lowerBound(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return left;}
}

性能：