- 难度：
简单 - 本题涉及算法：
暴力二分查找 - 思路：
暴力二分查找 - 类似题型:
题目 两个数组间的距离值
给你两个整数数组 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[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
示例 2：
输入：arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
输出：2
示例 3：
输入：arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
输出：1
方法一 暴力循环
java
public class Solution {
public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
int res = 0;
a: for (int i=0;i<arr1.length;i++) {
for (int j=0;j<arr2.length;j++) {
if (Math.abs(arr1[i] -arr2[j])<=d) {
continue a;
}
}
res++;
}
return res;
}
}
python
class Solution:
def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
res = 0
for num in arr1:
if all([abs(num - num2) > d for num2 in arr2]):
res +=1
return res
方法二 二分查找
在上一种方法中，要知道是否每一个 $y_j$ 是不是满足 $|x_i - y_j| > d$ ，我们枚举了所有 $y_j$ 。实际上我们只要找到大于等于 $x_i$ 的第一个 $y_j$ 和小于 $x$ 的第一个 $y_j$，看看它们满不满足这个性质就可以了。
我们可以对 arr2 进行排序，然后对于 arr1 中的每个元素 $x_i$ 在 arr2 中二分寻找上述的两个 $y_j$ 如果这两个元素满足性质，则所有元素都满足性质，将答案增加 11。
class Solution:
def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
arr2.sort()
cnt = 0
for x in arr1:
p = bisect.bisect_left(arr2, x)
if p == len(arr2) or abs(x - arr2[p]) > d:
if p == 0 or abs(x - arr2[p - 1]) > d:
cnt += 1
return cnt
PREVIOUS1389. 按既定顺序创建目标数组
NEXT1248. 统计「优美子数组」