两个数组间的距离值
给你两个整数数组 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
提示：
- 1 <= arr1.length, arr2.length <= 500
- -10^3 <= arr1[i], arr2[j] <= 10^3
- 0 <= d <= 100
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1385
解题思路分析：
这道题目的解释有些难以理解，简单翻一下，题目给出两个数组，我们需要在数组1中找到满足条件的数字个数，该条件为，数组1中的当前数字与数组2中的每一个数组的绝对值差都要大于d。
解法一：
理解了题意之后，其实题目本身并没有什么难度，题目中给出的数据规模最大是500，也就是说本题可以使用n平方的时间复杂度来解题。因此我们可以使用二层循环，用数组1中的每一个数字与数组2的每一个数字去比较，如果绝对值差都大于d，结果加一。
实现代码：
public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
int res=0;
for(int i=0;i<arr1.length;i++){
boolean isValid=true;
for(int j=0;j<arr2.length;j++){
if(Math.abs(arr1[i]-arr2[j])<=d){
isValid=false;
break;
}
}
if(isValid) res++;
}
return res;
}本解法执行时间为3ms。
Runtime: 3 ms, faster than 76.74% of Java online submissions for Find the Distance Value Between Two Arrays.
Memory Usage: 40.8 MB, less than 100.00% of Java online submissions for Find the Distance Value Between Two Arrays.
解法二：二分查找
本题我们可以将算法优化至n*logn，试想如果要保证一个数字与数组2中所有数字的绝对值差都大于d，那么我们只需要找出数组2中与当前数字最接近的两个数字，查看他们与当前数字的绝对值差是否大于d即可。因为与当前数字最接近的数字都大于d，那么与当前数字差值更大的数字的差值一定更加大于d。另外与当前数字最为接近的2个数字应该是：数组2中第一个小于等于当前数字的数，以及第一个大于等于当前数字 的数。我们可以使用二分查找的方式来找到这两个数字。关于这两个二分查找方式我们在以前的文章中有过详细的总结：LEETCODE常见算法之二分查找超详细白话讲解
实现代码：
public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
Arrays.sort(arr2);
int res=0;
for(int num : arr1){
int big=findFirstBigOrEqual(arr2,num);
int small=findFirstSmallOrEqual(arr2,num);
if(big-num>d&&num-small>d) res++;
}
return res;
}
int findFirstBigOrEqual(int[] arr, int target){
int low=0, high=arr.length-1;
while(low<=high){
int mid=(low+high)/2;
if(arr[mid]>=target){
high=mid-1;
}else{
low=mid+1;
}
}
return low==arr.length?Integer.MAX_VALUE:arr[low];
}
int findFirstSmallOrEqual(int[] arr, int target){
int low=0, high=arr.length-1;
while(low<=high){
int mid=(low+high)/2;
if(arr[mid]<=target){
low=mid+1;
}else{
high=mid-1;
}
}
return high==-1?Integer.MAX_VALUE:arr[high];
}由于本题的数据规模不大，nlogn与n方的处理时间上基本没有太大的区别，另外由于本方式需要给数组2进行排序，因此在执行效率上可能还会略低于解法1。
本解法执行时间为4ms。
Runtime: 4 ms, faster than 38.68% of Java online submissions for Find the Distance Value Between Two Arrays.
Memory Usage: 40.8 MB, less than 100.00% of Java online submissions for Find the Distance Value Between Two Arrays.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1385-find-the-distance-value-between-two-arrays-解题思路分析/