两个数组间的距离值

难度: 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

提示：

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

Submission

运行时间: 30 ms

内存: 16.1 MB

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        arr2.sort()
        ans = 0
        for x in arr1:
            left,right=0,len(arr2)-1
            while right > left+1:
                mid=(right+left)//2
                if arr2[mid]>x:
                    right = mid
                elif arr2[mid]==x:
                    break
                else:
                    left = mid
            if abs(arr2[(right+left)//2]-x)>d and abs(arr2[(right+left)//2+1]-x)>d:
                ans+=1
        return ans

Explain

首先对数组 arr2 进行排序。然后，对于 arr1 中的每个元素 x，使用二分搜索找到最接近 x 的元素在 arr2 中的位置，以判断是否存在 arr2 中的元素使得 |arr1[i] - arr2[j]| <= d。如果在 arr2 中找到的最近元素与 x 的差的绝对值大于 d，并且该位置附近的元素也满足此条件，那么 x 符合距离要求，距离值增加1。

时间复杂度: O(n log n + m log n)

空间复杂度: O(log n)

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        arr2.sort() # 对 arr2 进行排序
        ans = 0 # 初始化距离值为 0
        for x in arr1: # 遍历 arr1 中的每个元素
            left, right = 0, len(arr2) - 1 # 初始化二分搜索的左右界
            while right > left + 1: # 当左右界之间至少有一个元素时进行循环
                mid = (right + left) // 2 # 计算中点
                if arr2[mid] > x: # 如果中点元素大于 x，更新右界
                    right = mid
                elif arr2[mid] == x: # 如果找到等于 x 的元素，直接结束循环（不符合条件）
                    break
                else: # 如果中点元素小于 x，更新左界
                    left = mid
            # 检查最接近的两个元素是否都满足条件
            if abs(arr2[(right + left) // 2] - x) > d and abs(arr2[(right + left) // 2 + 1] - x) > d:
                ans += 1 # 如果满足条件，距离值增加 1
        return ans # 返回总的距离值

Explore

在这个算法中，对数组 arr2 进行排序是为了使用二分搜索技术来快速找到与 arr1 中元素 x 最接近的一个或两个元素。二分搜索依赖于有序数组来有效地减少搜索空间，从而加快查找速度。如果 arr2 未排序，则我们只能通过线性搜索来寻找最接近的元素，这将大大增加算法的时间复杂度。

在二分搜索过程中，如果找到一个与 x 完全相等的元素，则可以立即终止搜索，因为根据题目的定义，如果存在任何一个 arr2 中的 j 使得 |arr1[i] - arr2[j]| <= d 且 d >= 0，则这个 arr1[i] 的元素不符合距离值的要求。找到等于 x 的元素意味着差的绝对值为零，即不符合 |arr1[i] - arr2[j]| > d 的条件。因此，一旦找到等值元素，就确定了当前元素 x 不满足条件，无需进一步搜索。

在给定 arr2 已排序的情况下，对于任何元素 x，其可能与 x 满足 |arr1[i] - arr2[j]| <= d 的 arr2 中的元素一定是距离 x 最近的元素。这是因为，如果 x 与某个元素的差的绝对值超过 d，那么 x 与此元素更远的任何其他元素的差的绝对值也必定超过 d。因此，只需检查最接近 x 的两个元素（分别是左侧和右侧最近的元素），就足以确定是否有任何元素满足条件。这样做可以显著减少必要的计算量。

算法通过计算 abs(arr2[(right + left) // 2] - x) 来获取 arr2 中最接近 x 的元素与 x 的差的绝对值。如果这个差的绝对值大于 d，那么这表明当前元素与 x 的距离超过了 d，即它们不满足 |arr1[i] - arr2[j]| <= d 的条件。算法检查最接近 x 的两个元素，因为二分搜索的结果可能使 (right + left) // 2 的位置不一定是最接近 x 的元素，可能需要检查其相邻元素。若两个最接近的元素的差的绝对值都大于 d，则可以断定没有任何元素能使条件成立。