X

LEETCODE 1385. Find the Distance Value Between Two Arrays 解题思路分析

两个数组间的距离值

给你两个整数数组 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-解题思路分析/
Categories: leetcode
kwantong: