# LEETCODE 1385. Find the Distance Value Between Two Arrays 解题思路分析

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

```输入：arr1 = [4,5,8], arr2 = [10,9,1,8], d = 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[1]=5 我们有：
|5-10|=5 > d=2
|5-9|=4 > d=2
|5-1|=4 > d=2
|5-8|=3 > d=2
对于 arr1[2]=8 我们有：
|8-10|=2 <= d=2 |8-9|=1 <= d=2 |8-1|=7 > d=2
|8-8|=0 <= d=2```

```输入：arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3

```输入：arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6

• 1 <= arr1.length, arr2.length <= 500
• -10^3 <= arr1[i], arr2[j] <= 10^3
• 0 <= d <= 100

```public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
int res=0;
for(int i=0;i<arr1.length;i++){
boolean isValid=true;
for(int j=0;j<arr2.length;j++){
if(Math.abs(arr1[i]-arr2[j])<=d){
isValid=false;
break;
}
}
if(isValid) res++;
}
return res;
}```

Runtime: 3 ms, faster than 76.74% of Java online submissions for Find the Distance Value Between Two Arrays.

Memory Usage: 40.8 MB, less than 100.00% of Java online submissions for Find the Distance Value Between Two Arrays.

```public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
Arrays.sort(arr2);
int res=0;
for(int num : arr1){
int big=findFirstBigOrEqual(arr2,num);
int small=findFirstSmallOrEqual(arr2,num);
if(big-num>d&&num-small>d) res++;
}
return res;
}

int findFirstBigOrEqual(int[] arr, int target){
int low=0, high=arr.length-1;
while(low<=high){
int mid=(low+high)/2;
if(arr[mid]>=target){
high=mid-1;
}else{
low=mid+1;
}
}
return low==arr.length?Integer.MAX_VALUE:arr[low];
}

int findFirstSmallOrEqual(int[] arr, int target){
int low=0, high=arr.length-1;
while(low<=high){
int mid=(low+high)/2;
if(arr[mid]<=target){
low=mid+1;
}else{
high=mid-1;
}
}
return high==-1?Integer.MAX_VALUE:arr[high];
}```

Runtime: 4 ms, faster than 38.68% of Java online submissions for Find the Distance Value Between Two Arrays.

Memory Usage: 40.8 MB, less than 100.00% of Java online submissions for Find the Distance Value Between Two Arrays.