题目
给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。
| 「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 | arr1[i]-arr2[j] | <= d 。 |
示例
输入：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
题干
| arr1[i]-arr2[j] | <= d 为不符合要求 |
| arr1[i]-arr2[j] | > d 符合要求 |
对于arr[i] 如果有一项 arr2[j] 不符合要求距离值+1
思路
暴力循环
根据其定制的规则 循环数组arr1 在其中循环arr2
并且判断如果有不符合要求的 直接break循环 距离值+1
循环优化
对于嵌套循环的场景 我们考虑下是否可以将循环平铺 从循环中找到 优化点
从题干入手 即对于arr[i]来说 如何使得arr1[i]-arr2[j]足够小 让其不符合要求 如果这种极端情况都符合 那么肯定符合要求
也就是说 我们找到两个数使得传入的arr[i]与其足够小即可 第一个比这个大的数和第一个比这小的数
有没有熟悉的味道 这正好符合排序的顺序规则 我们只要把arr2数组排序 找到arr[i]在这个数组的位置 那么这个位置的前一个和后一个位置的数
我们不就可以知道 不就可以不通过循环判断是否符合条件了吗
解答
暴力循环
public class Solution {
public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
int distance = 0; int flag = 0 ;
for(int i=0;i<arr1.length;i++){
for(int j=0;j<arr2.length;j++){
int distanceD = Math.abs(arr2[j]-arr1[i]); //差值
if(distanceD<=d){ //不符合要求 直接break循环
flag=1;
break;
}
}//一次i循环 如果有不符合要求的distance+1
if (flag == 0 ) {
distance ++ ;
} else {
flag = 0 ;
}
}
return distance;
}
}
循环优化
public class Solution {
public static int findTheDistanceValue2(int[] arr1, int[] arr2, int d) {
Arrays.sort(arr2);
int distance = 0; int flag = 0 ;
for(int i=0;i<arr1.length;i++){
int p = binarySearch(arr2, arr1[i]); //找到这个数在数组的位置 比他大的位置
boolean ok = true;
if(p<arr2.length){ //如果是大的不符合
ok &= Math.abs(arr2[p]-arr1[i])>=d;
}
if (p - 1 >= 0 && p - 1 <= arr2.length) { //如果小的不符合
ok &= arr1[i] - arr2[p - 1] > d;
}
distance += ok ? 1 : 0; //同时不符合即distance+1
}
return distance;
}
public static int binarySearch(int[] arr, int target) {
int low = 0, high = arr.length - 1;
if (arr[high] < target) {
return high + 1;
}
while (low < high) {
int mid = (high - low) / 2 + low;
if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}
时空复杂度分析
如果采用暴力循环解法 时间复杂度为O(m*n) 空间复杂度为O(1) 没有用到辅助空间
如果采用只加个位解法 时间复杂度为O(nlogm)+O(mlogm) 前面部分是二分的时间 后面是排序的时间 空间复杂度为O(1)
解题技巧 总结形成套路
结语
此题涉及到 循环和条件判断 还有我们是否有办法根据条件去优化循环 去掉没有意义的循环
有的时候循环确实能解决问题 但是其所产生的代价也是巨大的 掌握优化循环的方法 能使得我们的算法更加的好
