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

Method 1: Brute-force

Method 2: Binary search

Python3

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        return sum(all(abs(a - b) > d for b in arr2) for a in arr1)

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        def check(a):
            idx = bisect_left(arr2, a - d)
            if idx != len(arr2) and arr2[idx] <= a + d:
                return False
            return True

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

Java

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

    private boolean check(int[] arr, int a, int d) {
        for (int b : arr) {
            if (Math.abs(a - b) <= d) {
                return false;
            }
        }
        return true;
    }
}

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 left = 0, right = arr.length;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid] >= a - d) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        if (left != arr.length && arr[left] <= a + d) {
            return false;
        }
        return true;
    }
}

C++

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        int ans = 0;
        for (int& a : arr1)
            ans += check(arr2, a, d);
        return ans;
    }

    bool check(vector<int>& arr, int a, int d) {
        for (int& b : arr)
            if (abs(a - b) <= d)
                return false;
        return true;
    }
};

class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
        sort(arr2.begin(), arr2.end());
        int ans = 0;
        for (int& a : arr1)
            if (check(arr2, a, d))
                ++ans;
        return ans;
    }

    bool check(vector<int>& arr, int a, int d) {
        int idx = lower_bound(arr.begin(), arr.end(), a - d) - arr.begin();
        if (idx != arr.size() && arr[idx] <= a + d) return false;
        return true;
    }
};

Go

func findTheDistanceValue(arr1 []int, arr2 []int, d int) int {
	check := func(arr []int, a int) bool {
		for _, b := range arr {
			if -d <= a-b && a-b <= d {
				return false
			}
		}
		return true
	}

	ans := 0
	for _, a := range arr1 {
		if check(arr2, a) {
			ans++
		}
	}
	return ans
}

func findTheDistanceValue(arr1 []int, arr2 []int, d int) int {
	sort.Ints(arr2)
	check := func(a int) bool {
		left, right := 0, len(arr2)
		for left < right {
			mid := (left + right) >> 1
			if arr2[mid] >= a-d {
				right = mid
			} else {
				left = mid + 1
			}
		}
		if left != len(arr2) && arr2[left] <= a+d {
			return false
		}
		return true
	}
	ans := 0
	for _, a := range arr1 {
		if check(a) {
			ans++
		}
	}
	return ans
}

...