1385. 两个数组间的距离值 Easy
给你两个整数数组 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
示例 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
解题思路
输入： 两个整数数组 arr1 arr2
输出： 返回两个数组之间的距离值
本题属于二分查找类问题。
这道题的核心就是：
对每个 arr1[i]，二分查找 arr2 是否存在落在 [i-d, i+d] 范围内的数，如果没有，结果 +1。
我们可以先对 arr2 排序方便后续二分查找
遍历 arr1 中的每个元素 x，在 arr2 中用二分查找，判断是否有任意一个数载 [x - d, x + d] 中
代码实现
class Solution:
def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
# 二分查找：判断 arr2 中是否存在值在 [low, high] 范围内
def in_range(nums, low, high):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
# 如果 nums[mid] 落在范围内，直接返回 True
if low <= nums[mid] <= high:
return True
elif nums[mid] < low:
# 太小，继续往右边查找
left = mid + 1
else:
# 太大，继续往左边查找
right = mid - 1
# 没找到在范围内的数，返回 False
return False
arr2.sort() # 对 arr2 排序，方便二分查找
count = 0 # 统计符合条件的元素个数
for num in arr1:
# 如果 arr2 中没有任何一个数与 num 的差值小于等于 d
if not in_range(arr2, num - d, num + d):
count += 1
return count/**
* @param {number[]} arr1
* @param {number[]} arr2
* @param {number} d
* @return {number}
*/
var findTheDistanceValue = function(arr1, arr2, d) {
function inRange(nums, low, high) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] >= low && nums[mid] <= high) {
return true;
}
if (nums[mid] < low) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
arr2.sort((a, b) => a - b);
let count = 0;
for (let x of arr1) {
if (!inRange(arr2, x - d, x + d)) {
count ++;
}
}
return count;
};复杂度分析
时间复杂度：O(log n)
空间复杂度：O(1)