| 题目链接 | 1385. 两个数组间的距离值 |
|---|---|
| 思路 | 二分查找 |
| 题解链接 | 官方题解 |
| 关键点 | 标准库的利用；二分循环不变式（开区间）：nums[left] < target && nums[right] >= target |
| 时间复杂度 | \(O((n+m)\log m)\) |
| 空间复杂度 | \(O(1)\) |
代码实现：
class Solution:
def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
arr2.sort()
n = len(arr2)
def lower_bound(val):
left, right = -1, n
while left+1 < right:
mid = (left+right)//2
if arr2[mid] < val:
left = mid
else:
right = mid
return right
cnt = 0
for x in arr1:
p = lower_bound(x)
if (p == n or abs(x - arr2[p]) > d) and (
p == 0 or abs(x - arr2[p - 1]) > d
):
cnt += 1
return cnt
Python-官方库
class Solution:
def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
arr2.sort()
cnt = 0
for x in arr1:
p = bisect_left(arr2, x)
if (p == len(arr2) or abs(x - arr2[p]) > d) and (
p == 0 or abs(x - arr2[p - 1]) > d
):
cnt += 1
return cnt