// BF time: O(m * n) space: O(1) publicstaticintfindTheDistanceValue_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≤y≤x+d,那么arr1中的数 x 就不满足要求。
publicintfindTheDistanceValue(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; }
publicbooleanbinarySearch(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) { returntrue; } elseif (arr[mid] < low) { left = mid + 1; } elseif (arr[mid] > high) { right = mid - 1; } }