跳至主要內容

1385. 两个数组间的距离值

1385. 两个数组间的距离值

🟢   🔖  数组 双指针 二分查找 排序  🔗 力扣open in new window LeetCodeopen in new window

题目

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

题目大意

给你两个整数数组 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[0]=4 符合距离要求

对于 arr1[1]=5 我们有：

|5-10|=5 > d=2 |5-9|=4 > d=2 |5-1|=4 > d=2 |5-8|=3 > d=2

所以 arr1[1]=5 也符合距离要求

对于 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[0]=4 和 arr1[1]=5 两个符合距离要求，距离值为 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

解题思路

  1. 排序数组 arr2：

    • 对数组 arr2 进行排序。这样做的目的是在后续的二分查找中能够更高效地判断 arr1 中每个元素是否与 arr2 中的元素距离小于等于 d。

  2. 遍历 arr1 中的每个元素：

    • 对于 arr1 中的每个元素，希望和 arr2 中的所有元素的差的绝对值都大于 d。
    • 因此，对于每个元素 char，计算一个区间 [char - d, char + d]，如果 arr2 中有任何元素落在这个区间内，都不符合距离要求。

  3. 二分查找：

    • 使用二分查找来判断 arr2 中是否有元素在 char - d 到 char + d 的范围内。如果有，就认为这个元素不符合要求，跳过；否则，增加结果计数。
    • 通过二分查找，能够高效地找到是否有元素在指定范围内。

  4. 返回结果：

    • 最终返回符合条件的 arr1 中元素的个数。

复杂度分析

  • 时间复杂度：O(n log n + m log n)，其中 n 是 arr2 的长度，m 是 arr1 的长度。

    • 对 arr2 进行排序的时间复杂度是 O(n log n)。
    • 对于 arr1 中的每个元素，使用二分查找在 arr2 中查找是否有元素在 [char - d, char + d] 范围内。每次二分查找的时间复杂度是 O(log n)，总共查找 m 次，时间复杂度是 O(m log n)。

  • 空间复杂度：O(1)，使用了常数量级的空间。

代码

/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @param {number} d
 * @return {number}
 */
var findTheDistanceValue = function (arr1, arr2, d) {
	arr2.sort((a, b) => a - b);

	let distance = 0;
	for (let num of arr1) {
		// 检查 arr2 中是否有元素落在 [char - d, char + d] 区间内
		if (checkDistance(arr2, num - d, num + d)) {
			distance++;
		}
	}
	return distance;
};

var checkDistance = function (arr, from, to) {
	// 二分查找
	let left = 0,
		right = arr.length - 1;
	while (left <= right) {
		const mid = ((left + right) / 2) | 0;
		if (arr[mid] >= from && arr[mid] <= to) {
			return false;
		} else if (arr[mid] < from) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	return true;
};