[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(m×n)$，其中$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. 😉😃💗