- 题目
- 博主的话
- 暴力解法
- 二分法解决
给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。
「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。
示例 1：
输入：arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
输出：2
解释：对于 arr1[0]=4 我们有：
|4-10|=6 > d=2
|4-9|=5 > d=2
|4-1|=3 > d=2
|4-8|=4 > d=2
所以 arr1[0]=4 符合距离要求对于 arr1[1]=5 我们有：
|5-10|=5 > d=2
|5-9|=4 > d=2
|5-1|=4 > d=2
|5-8|=3 > d=2
所以 arr1[1]=5 也符合距离要求对于 arr1[2]=8 我们有：
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2
存在距离小于等于 2 的情况，不符合距离要求故而只有 arr1[0]=4 和 arr1[1]=5 两个符合距离要求，距离值为 2
1 <= arr1.length, arr2.length <= 500
-10^3 <= arr1[i], arr2[j] <= 10^3
0 <= d <= 100
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-the-distance-value-between-two-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这个题虽说是简单题，也确实使用暴力解法的话，运行结果是很客观的，并且暴力解法的执行时间是比二分解法的执行时间要短的。
但是这个题我们去尽量换思维的方式去解题，在我们平时做练习的时候，不能为解题而且做题，重要的是思维。
也是因为这个题用二分的话，不是很好理解，所以博主也就分享了这道题。
暴力解法就是两个for循环嵌套，对两个数组进行遍历，一个一个的查找找出结果来。
暴力这就不对代码进行具体解释了，不难很简单
class Solution {
public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
int len1 = arr1.length, len2 = arr2.length;//获得两个数组的长度
int res = 0;//最后返回的值
for (int i = 0; i < len1; i++) {
res++;//每次开始对数组1里面的数进行判断的时候先对结果加1
for (int j = 0; j < len2; j++) {
//对第二个数组进行发现只要出现一例不合格的，就减去前面加的一个，然后就可以终止对数组2的遍历循环了。
if (Math.abs(arr1[i] - arr2[j]) <= d) {
res--;
break;
}
}
}
return res;
}
}
二分法解决
在使用二分法的时候，我们认为每次是从数组1当中拿数据，然后和数组2中的元素进行比较。
因为使用了二分法，所以我们对数组2进行排序，又因为在这个当中，数组中的元素大小可以为负数，所以单纯的通过思考是及其难想明白的。
在这里我们借用画图来思考这个问题。
相信通过这个图去理解这个题就不会很困难。
下来看代码：
class Solution {
public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
Arrays.sort(arr2);//对数组2进行从小到大的排序
int ans = 0;//最终结果返回
int len1 = arr1.length, len2 = arr2.length;
for (int i = 0; i < len1; i++) {
int min = arr1[i] - d;//获得当前arr1数组中元素结合d区间的最小值
int max = arr1[i] + d;//获得当前arr1数组中元素结合d区间的最大值
//若判断出arr2数组中的最大元素小于区间最小值，数组最小值大于区间最大值，直接给予通过
if (arr2[0] > max || arr2[len2 - 1] < min) {
ans++;
continue;
}
//下来就是标准的二分查找
int left = 0, right = len2 - 1;
boolean res = false;
while (left <= right) {
int mid = left + (right - left) / 2;
//当中间值在区间内的时候，就可以结束循环了
if (arr2[mid] >= min && arr2[mid] <= max) {
res = true;
break;
} else if (arr2[mid] < min) {
left = mid + 1;
} else if (arr2[mid] > max) {
right = mid - 1;
}
}
//最后再决定对当前这个值是否合格
if (!res) {
ans++;
}
}
return ans;
}
}
如还有什么疑问，欢迎在评论区讨论。
