LeetCode（Binary Search)1385. Find the Distance Value Between Two Arrays

水深无声 2023-09-25 23:08 41阅读 0赞

# 1.问题 #

Given two integer arrays arr1 and arr2, and the integer d, return the distance value between the two arrays.

The distance value is defined as the number of elements arr1\[i\] such that there is not any element arr2\[j\] where |arr1\[i\]-arr2\[j\]| <= d.

Example 1:

> Input: arr1 = \[4,5,8\], arr2 = \[10,9,1,8\], d = 2  
> Output: 2  
> Explanation:  
> For arr1\[0\]=4 we have:  
> |4-10|=6 > d=2  
> |4-9|=5 > d=2  
> |4-1|=3 > d=2  
> |4-8|=4 > d=2  
> For arr1\[1\]=5 we have:  
> |5-10|=5 > d=2  
> |5-9|=4 > d=2  
> |5-1|=4 > d=2  
> |5-8|=3 > d=2  
> For arr1\[2\]=8 we have:  
> |8-10|=2 <= d=2  
> |8-9|=1 <= d=2  
> |8-1|=7 > d=2  
> |8-8|=0 <= d=2

Example 2:

> Input: arr1 = \[1,4,2,3\], arr2 = \[-4,-3,6,10,20,30\], d = 3  
> Output: 2

Example 3:

> Input: arr1 = \[2,1,100,3\], arr2 = \[-5,-2,10,-3,7\], d = 6  
> Output: 1

Constraints:

*  1 <= arr1.length, arr2.length <= 500
 *  \-1000 <= arr1\[i\], arr2\[j\] <= 1000
 *  0 <= d <= 100

# 2. 解题思路 #

## 方法1： ##

> 1.遍历arr1中的每个元素，对于每个元素，都要遍历arr2中的每个元素。  
> 2.计算两个元素之间的绝对差值，如果差值大于d，则将计数器加1。  
> 3.最终返回计数器的值，它表示arr1中有多少个元素与arr2中的每个元素的绝对差值都大于d。  
> **注意事项：**  
> 在第二步中，我们应该使用绝对差值而不是简单的减法运算来计算两个元素之间的距离。  
> 在第三步中，我们应该将计数器增加的条件更改为差值大于d，而不是小于等于d。

## 方法2： ##

> 排序 + 二分查找  
> 首先，我们将arr2中的所有元素进行排序，然后遍历arr1中的每个元素，并使用二分查找来查找在arr2中距离当前元素最近的元素。如果最近的元素的绝对差值大于d，则将计数器加1。时间复杂度为O(nlogn)。

## 方法3： ##

> 使用哈希表来存储arr2中的所有元素，并遍历arr1中的每个元素。对于arr1中的每个元素，我们可以使用哈希表来查找与其距离小于等于d的元素。时间复杂度为O(n)。

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        
            int count = 0; // 初始化计数器
            for(int i = 0; i < arr1.length; i++){
         // 遍历arr1中的每个元素
                boolean flag = true; // 初始化flag为true
                for(int j = 0; j < arr2.length; j++){
         // 遍历arr2中的每个元素
                    if(Math.abs(arr1[i] - arr2[j]) <= d){
         // 如果两个元素的距离小于等于d
                        flag = false; // 将flag设置为false
                        break; // 退出arr2的循环
                    }
                }
                if(flag){
         // 如果flag仍为true
                    count++; // 将计数器增加1
                }
            }
            return count; // 返回计数器的值
        }
    }

> 增加了一个boolean类型的flag来表示arr1中的当前元素是否与任何一个arr2中的元素距离小于等于d。如果存在这样的元素，则将flag设置为false，并退出arr2的循环。如果没有这样的元素，则计数器增加1。最后返回计数器的值，它表示符合条件的元素的数量。

## 代码2： ##

class Solution {
        
        public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        
            Arrays.sort(arr2); // 对arr2中的元素进行排序
            int count = 0;
            for(int i = 0; i < arr1.length; i++){
         // 遍历arr1中的每个元素
                int index = Arrays.binarySearch(arr2, arr1[i]); // 使用二分查找来查找最近的元素
                if(index < 0){
         // 如果找不到元素，则将其插入到正确的位置
                    index = -(index + 1);
                }
                if((index == 0 || arr1[i] - arr2[index - 1] > d) && (index == arr2.length || arr2[index] - arr1[i] > d)){
        
                    // 如果最近的元素的绝对差值大于d，则将计数器加1
                    count++;
                }
            }
            return count; // 返回计数器的值
        }
    }

> 使用了排序和二分查找来优化暴力解法，代码中的注释已经解释了每一步所做的事情，主要思路是遍历arr1中的每个元素，然后使用二分查找来查找arr2中与其距离小于等于d的元素，如果找到了这样的元素，则将计数器加1。最后，返回计数器的值作为答案。

class Solution {
        
        public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        
            int distance = 0; // 初始化距离值
            
            Arrays.sort(arr2); // 对arr2中的元素进行排序
            
            for (int num1 : arr1) {
         // 遍历arr1中的每个元素
                // 使用二分查找来查找与当前元素距离小于等于d的元素
                if (Arrays.binarySearch(arr2, num1 - d) == Arrays.binarySearch(arr2, num1 + d)) {
        
                    distance++; // 如果存在这样的元素，则将计数器加1
                }
            }
            
            return distance; // 返回计数器的值
        }
    }

## 代码3： ##

class Solution {
        
        public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        
            Set<Integer> set = new HashSet<>();
            for(int num : arr2){
         // 将arr2中的所有元素添加到哈希表中
                set.add(num);
            }
            int count = 0;
            for(int num : arr1){
         // 遍历arr1中的每个元素
                boolean flag = true;
                for(int i = num - d; i <= num + d; i++){
         // 查找距离当前元素小于等于d的元素
                    if(set.contains(i)){
        
                        flag = false;
                        break;
                    }
                }
                if(flag){
         // 如果不存在这样的元素，则将计数器加1
                    count++;
                }
            }
            return count; // 返回计数器的值
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，41人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode（Binary Search)1385. Find the Distance Value Between Two Arrays

1.问题 Given two integer arrays arr1 and arr2, and the integer d, return the distance v

水深无声/ 2023年09月25日 23:08/ 0 赞/ 42 阅读

相关 LeetCode | 1385. Find the Distance Value Between Two Arrays两个数组间的距离值【Python】

> LeetCode 1385. Find the Distance Value Between Two Arrays两个数组间的距离值【Easy】【Python】【暴力】

客官°小女子只卖身不卖艺/ 2023年07月17日 14:10/ 0 赞/ 2 阅读

相关《PDARTS：Bridging the Depth Gap between Search and Evaluation》论文笔记

参考代码：[pdarts][] 1. 概述 > 导读：这篇文章在DARTS的工作的基础上，指出直接使用DARTS方法得到的模型搜索结果直接运用到大数据集（如ImageN

缺乏、安全感/ 2022年12月27日 04:44/ 0 赞/ 44 阅读

相关 LeetCode - Easy - 783. Minimum Distance Between BST Nodes

Topic Tree Depth-first Search Recursion Description [https://leetcode.co

怼烎@/ 2022年10月06日 08:53/ 0 赞/ 105 阅读

相关【LeetCode】783. Minimum Distance Between BST Nodes

Given a Binary Search Tree (BST) with the root node `root`, return the minimum differenc

电玩女神/ 2022年05月18日 09:26/ 0 赞/ 110 阅读

相关 Distance between two points

This small operation calcuates the distance between two points. The routine can work in

心已赠人/ 2022年01月06日 09:11/ 0 赞/ 100 阅读

相关 For the distance calculation

A UDF (user defined function) to calculate distance between two zip codes as follow: 首

ゝ一世哀愁。/ 2021年12月16日 01:27/ 0 赞/ 143 阅读

相关 find-the-distance-from-a-3d-point-to-a-line-segment

[https://stackoverflow.com/questions/4858264/find-the-distance-from-a-3d-point-to-a-line

水深无声/ 2021年10月15日 23:17/ 0 赞/ 226 阅读

相关 Clearing Search Values

<table style="font:12px/19px Tahoma, 'Microsoft Yahei';color:444444;text-transform:none;

太过爱你忘了你带给我的痛/ 2021年10月15日 20:35/ 0 赞/ 196 阅读

相关 153. Find Minimum in Rotated Sorted Array(leetcode, binary search)

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/ leetcod

╰+哭是因爲堅強的太久メ/ 2021年09月30日 14:38/ 0 赞/ 218 阅读