两个数组间的距离值
难度:
标签:
题目描述
代码结果
运行时间: 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 进行排序?
▷🦆
在二分搜索过程中,为什么要终止搜索当找到一个等于 x 的元素,这会对结果有什么影响?
▷🦆
在检查是否存在 arr2 中的元素使得 |arr1[i] - arr2[j]| <= d 时,为什么只检查最接近 x 的两个元素而不是所有元素?
▷🦆
算法在判断两个最接近的元素是否满足条件时,为什么使用了 abs(arr2[(right + left) // 2] - x) > d 来进行判断?
▷