関小君刷题记

两个数组间的距离值

给你两个整数数组 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.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1385-find-the-distance-value-between-two-arrays-解题思路分析/