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

By Long Luo

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

方法一:模拟

对于arr1arr1数组中的每一个元素xx,枚举数组arr2arr2中的每一个元素yy,检查是否对于每一个yy都有xy>d|x - y| > d,如果是,就将答案增加11

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(m×n)O(m×n),其中arr1arr1中元素个数为mmarr2arr2中元素个数为nn

  • 空间复杂度:O(1)O(1)

方法二: 二分搜索

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

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

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

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)logm)O((n+m)logm),给arr2排序的时间代价是O(mlogm)O(m \log m),对于arr1中的每个元素都在arr2中二分的时间代价是O(nlogm)O(n \log m),故总时间复杂度为O((n+m)logm)O((n+m)logm)

  • 空间复杂度:O(1)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. 😉😃💗