README_EN.md

1385. Find the Distance Value Between Two Arrays

中文文档

Description

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

Solutions

Python3

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        def check(a: int) -> bool:
            i = bisect_left(arr2, a - d)
            return i == len(arr2) or arr2[i] > a + d

        arr2.sort()
        return sum(check(a) for a in arr1)

Java

class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int ans = 0;
        for (int a : arr1) {
            if (check(arr2, a, d)) {
                ++ans;
            }
        }
        return ans;
    }

    private boolean check(int[] arr, int a, int d) {
        int l = 0, r = arr.length;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (arr[mid] >= a - d) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l >= arr.length || arr[l] > a + d;
    }
}

C++

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        auto check = [&](int a) -> bool {
            auto it = lower_bound(arr2.begin(), arr2.end(), a - d);
            return it == arr2.end() || *it > a + d;
        };
        sort(arr2.begin(), arr2.end());
        int ans = 0;
        for (int& a : arr1) {
            ans += check(a);
        }
        return ans;
    }
};

Go

func findTheDistanceValue(arr1 []int, arr2 []int, d int) (ans int) {
	sort.Ints(arr2)
	for _, a := range arr1 {
		i := sort.SearchInts(arr2, a-d)
		if i == len(arr2) || arr2[i] > a+d {
			ans++
		}
	}
	return
}

TypeScript

function findTheDistanceValue(arr1: number[], arr2: number[], d: number): number {
    const check = (a: number) => {
        let l = 0;
        let r = arr2.length;
        while (l < r) {
            const mid = (l + r) >> 1;
            if (arr2[mid] >= a - d) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l === arr2.length || arr2[l] > a + d;
    };
    arr2.sort((a, b) => a - b);
    let ans = 0;
    for (const a of arr1) {
        if (check(a)) {
            ++ans;
        }
    }
    return ans;
}

Rust

impl Solution {
    pub fn find_the_distance_value(arr1: Vec<i32>, mut arr2: Vec<i32>, d: i32) -> i32 {
        arr2.sort();
        let n = arr2.len();
        let mut res = 0;
        for &num in arr1.iter() {
            let mut left = 0;
            let mut right = n - 1;
            while left < right {
                let mid = left + (right - left) / 2;
                if arr2[mid] <= num {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            if i32::abs(num - arr2[left]) <= d || (left != 0 && i32::abs(num - arr2[left - 1]) <= d) {
                continue;
            }
            res += 1;
        }
        res
    }
}

...