[Leetcode][1385. 两个数组间的距离值] 2种方法：模拟 和 二分搜索

By Long Luo

这篇文章是 Leetcode 1385. 两个数组间的距离值 的 力扣社区题解 。

方法一：模拟

对于 $arr1$ 数组中的每一个元素 $x$，枚举数组 $arr2$ 中的每一个元素 $y$，检查是否对于每一个 $y$ 都有 $|x - y| > d$，如果是，就将答案增加 $1$。

// BF time: O(m * n) space: O(1)
public static int findTheDistanceValue_bf(int[] arr1, int[] arr2, int d) {
	int ans = 0;
	for (int x : arr1) {
		boolean flag = true;
		for (int y : arr2) {
			if (Math.abs(x - y) <= d) {
				flag = false;
			}
		}

		ans += flag ? 1 : 0;
	}

	return ans;
}

复杂度分析

• 时间复杂度：$O(mn)$，其中 $arr1$ 中元素个数为 $m$，$arr2$ 中元素个数为 $n$。

• 空间复杂度：$O(1)$。

方法二： 二分搜索

在方法一中，要知道是否每一个 $y$ 是不是满足 $|x - y| > d$，我们枚举了所有 $y$。

实际上因为 $d >= 0$，假如arr2存在某个 $y$ 满足 $x - d \le y \le x + d$，那么arr1中的数 $x$ 就不满足要求。

先对arr2进行排序，之后枚举arr1每个元素 $x$，利用二分搜索来判断 $x$ 是否满足要求。

public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
	Arrays.sort(arr2);
	int ans = 0;
	for (int x : arr1) {
		int low = x - d;
		int high = x + d;
		if (!binarySearch(arr2, low, high)) {
			ans++;
		}
	}

	return ans;
}

public boolean binarySearch(int[] arr, int low, int high) {
	int left = 0;
	int right = arr.length - 1;
	while (left <= right) {
		int mid = left + (right - left) / 2;
		if (arr[mid] >= low && arr[mid] <= high) {
			return true;
		} else if (arr[mid] < low) {
			left = mid + 1;
		} else if (arr[mid] > high) {
			right = mid - 1;
		}
	}

	return false;
}

复杂度分析

• 时间复杂度：$O((n+m)logm)$，给 arr2 排序的时间代价是 $O(m \log m)$，对于arr1中的每个元素都在arr2中二分的时间代价是 $O(n \log m)$，故总时间复杂度为 $O((n+m)logm)$。

• 空间复杂度：$O(1)$。

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗