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
| 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; }
|
复杂度分析
方法二: 二分搜索
在方法一中,要知道是否每一个 y 是不是满足 ∣x−y∣>d,我们枚举了所有 y。
实际上因为 d>=0,假如arr2
存在某个 y 满足 x−d≤y≤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; }
|
复杂度分析
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. 😉😃💗