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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

By Long Luo

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

方法一：模拟

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 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\) 是否满足要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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) \log m)\)，给 arr2 排序的时间代价是 \(O(m \log m)\)，对于arr1中的每个元素都在arr2中二分的时间代价是 \(O(n \log m)\)，故总时间复杂度为 \(O((n+m) \log m)\)。
  • 空间复杂度：\(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. 😉😃💗