leetcode
leetcode 1251 ~ 1300
两个数组间的距离值

两个数组间的距离值

难度:

标签:

题目描述

代码结果

运行时间: 30 ms, 内存: 16.1 MB


/*
 * 思路:
 * 使用Java Stream API实现,利用stream()方法对arr1进行流处理,
 * 在流中使用allMatch()方法检查arr2中的每个元素,
 * 是否所有|arr1[i] - arr2[j]|都大于d,
 * 如果是,则计数器增加。
 */
import java.util.Arrays;

public class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        return (int) Arrays.stream(arr1)
                .filter(num1 -> Arrays.stream(arr2)
                        .allMatch(num2 -> Math.abs(num1 - num2) > d))
                .count();
    }
}

解释

方法:

首先对数组 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)

代码细节讲解

🦆
为什么在这个算法中首先需要对数组 arr2 进行排序?
在这个算法中,对数组 arr2 进行排序是为了使用二分搜索技术来快速找到与 arr1 中元素 x 最接近的一个或两个元素。二分搜索依赖于有序数组来有效地减少搜索空间,从而加快查找速度。如果 arr2 未排序,则我们只能通过线性搜索来寻找最接近的元素,这将大大增加算法的时间复杂度。
🦆
在二分搜索过程中,为什么要终止搜索当找到一个等于 x 的元素,这会对结果有什么影响?
在二分搜索过程中,如果找到一个与 x 完全相等的元素,则可以立即终止搜索,因为根据题目的定义,如果存在任何一个 arr2 中的 j 使得 |arr1[i] - arr2[j]| <= d 且 d >= 0,则这个 arr1[i] 的元素不符合距离值的要求。找到等于 x 的元素意味着差的绝对值为零,即不符合 |arr1[i] - arr2[j]| > d 的条件。因此,一旦找到等值元素,就确定了当前元素 x 不满足条件,无需进一步搜索。
🦆
在检查是否存在 arr2 中的元素使得 |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) > d 来进行判断?
算法通过计算 abs(arr2[(right + left) // 2] - x) 来获取 arr2 中最接近 x 的元素与 x 的差的绝对值。如果这个差的绝对值大于 d,那么这表明当前元素与 x 的距离超过了 d,即它们不满足 |arr1[i] - arr2[j]| <= d 的条件。算法检查最接近 x 的两个元素,因为二分搜索的结果可能使 (right + left) // 2 的位置不一定是最接近 x 的元素,可能需要检查其相邻元素。若两个最接近的元素的差的绝对值都大于 d,则可以断定没有任何元素能使条件成立。

相关问题