题目描述
思路解析动画文字版
记牢一句:arr1 的每个数,去 arr2 找有没有距离 ≤ 2 的近邻;找不到才达标。下面每帧都在套这句。
总览 · arr1 在上排,arr2 在侧栏：arr1 是上面这排 [3,4,10,7],arr2 放在右边侧栏 [9,8,0,7]。要做的事:把 arr1 的每个数轮流拿出来,到 arr2 里查有没有距离不超过 2 的邻居。一个邻居都没有的才算达标,最后数出有几个。先从第一个数 3 开始。
检查 arr1[0] = 3：现在轮到 arr1 的第 0 个数,值是 3。去 arr2 这排里挨个看,有没有哪个数跟它的距离不超过 2。只要找到一个,3 就出局;一个都没有,它才达标。
比 arr2[0] = 9 · 距离 6：arr2 的第 0 个数是 9,算一下距离 |3 减 9| = 6。6 比 2 大,这个数离得够远,接着看下一个。
比 arr2[1] = 8 · 距离 5：arr2 的第 1 个数是 8,算一下距离 |3 减 8| = 5。5 比 2 大,这个数离得够远,接着看下一个。
比 arr2[2] = 0 · 距离 3：arr2 的第 2 个数是 0,算一下距离 |3 减 0| = 3。3 比 2 大,这个数离得够远,接着看下一个。
比 arr2[3] = 7 · 距离 4：arr2 的第 3 个数是 7,算一下距离 |3 减 7| = 4。4 比 2 大,这个数离得够远,接着看下一个。
结算 · 3 达标：arr2 整排都看完了,没有任何一个数跟 3 的距离落在 2 以内,所以 3 达标,标绿,计入答案。已确认达标 1 个。
检查 arr1[1] = 4：现在轮到 arr1 的第 1 个数,值是 4。去 arr2 这排里挨个看,有没有哪个数跟它的距离不超过 2。只要找到一个,4 就出局;一个都没有,它才达标。
比 arr2[0] = 9 · 距离 5：arr2 的第 0 个数是 9,算一下距离 |4 减 9| = 5。5 比 2 大,这个数离得够远,接着看下一个。
比 arr2[1] = 8 · 距离 4：arr2 的第 1 个数是 8,算一下距离 |4 减 8| = 4。4 比 2 大,这个数离得够远,接着看下一个。
比 arr2[2] = 0 · 距离 4：arr2 的第 2 个数是 0,算一下距离 |4 减 0| = 4。4 比 2 大,这个数离得够远,接着看下一个。
比 arr2[3] = 7 · 距离 3：arr2 的第 3 个数是 7,算一下距离 |4 减 7| = 3。3 比 2 大,这个数离得够远,接着看下一个。
结算 · 4 达标：arr2 整排都看完了,没有任何一个数跟 4 的距离落在 2 以内,所以 4 达标,标绿,计入答案。已确认达标 2 个。
检查 arr1[2] = 10：现在轮到 arr1 的第 2 个数,值是 10。去 arr2 这排里挨个看,有没有哪个数跟它的距离不超过 2。只要找到一个,10 就出局;一个都没有,它才达标。
比 arr2[0] = 9 · 距离 1：arr2 的第 0 个数是 9,算一下距离 |10 减 9| = 1。1 不超过 2,这就是一个近邻,出局信号亮了,10 注定达不了标。后面几个还是顺手扫完看清楚。
比 arr2[1] = 8 · 距离 2：arr2 的第 1 个数是 8,算一下距离 |10 减 8| = 2。2 不超过 2,这就是一个近邻,出局信号亮了,10 注定达不了标。后面几个还是顺手扫完看清楚。
比 arr2[2] = 0 · 距离 10：arr2 的第 2 个数是 0,算一下距离 |10 减 0| = 10。10 比 2 大,这个数离得够远,接着看下一个。
比 arr2[3] = 7 · 距离 3：arr2 的第 3 个数是 7,算一下距离 |10 减 7| = 3。3 比 2 大,这个数离得够远,接着看下一个。
结算 · 10 出局：这排里出现过距离不超过 2 的数,说明 10 有近邻,不达标,标红,不计入。已确认达标 2 个。
检查 arr1[3] = 7：现在轮到 arr1 的第 3 个数,值是 7。去 arr2 这排里挨个看,有没有哪个数跟它的距离不超过 2。只要找到一个,7 就出局;一个都没有,它才达标。
比 arr2[0] = 9 · 距离 2：arr2 的第 0 个数是 9,算一下距离 |7 减 9| = 2。2 不超过 2,这就是一个近邻,出局信号亮了,7 注定达不了标。后面几个还是顺手扫完看清楚。
比 arr2[1] = 8 · 距离 1：arr2 的第 1 个数是 8,算一下距离 |7 减 8| = 1。1 不超过 2,这就是一个近邻,出局信号亮了,7 注定达不了标。后面几个还是顺手扫完看清楚。
比 arr2[2] = 0 · 距离 7：arr2 的第 2 个数是 0,算一下距离 |7 减 0| = 7。7 比 2 大,这个数离得够远,接着看下一个。
比 arr2[3] = 7 · 距离 0：arr2 的第 3 个数是 7,算一下距离 |7 减 7| = 0。0 不超过 2,这就是一个近邻,出局信号亮了,7 注定达不了标。后面几个还是顺手扫完看清楚。
结算 · 7 出局：这排里出现过距离不超过 2 的数,说明 7 有近邻,不达标,标红,不计入。已确认达标 2 个。
完成 · 距离值 2：arr1 的四个数都查完了。3 和 4 在 arr2 里找不到距离 ≤ 2 的近邻,达标涂绿;10 和 7 都有挨得很近的邻居,出局涂红。所以距离值就是这两个达标的数,答案 2,跟开头说的对上了。
边界:d=0 时只有相等才算近邻;全都找得到近邻则答案 0;只有离群的大数能达标。
面试重点:暴力 O(m·n) 对排序二分 O((m+n)log n);排序后只看第一个不小于 a 减 d 的候选;Java 的 binarySearch 负返回值要还原。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int: arr2.sort() ans = 0 for x in arr1: i = bisect_left(arr2, x - d) ans += i == len(arr2) or arr2[i] > x + d return ans复杂度
- 时间：O((m+n)·log n)，m、n 分别是 arr1、arr2 的长度。参考代码先给 arr2 排序是 O(n log n),再对 arr1 的每个数做一次二分各 O(log n),合起来 m log n,总体 O((m+n)·log n)。动画演示的暴力逐个比对则是 O(m·n),数据小时也够用
- 空间：O(1) 到 O(n)，除排序外只用了计数器等常数个变量。空间按峰值看排序内部开销:不计排序记 O(1);要计的话,C++ 与 Java 的排序是 O(log n) 递归栈,Python 的 list.sort 最坏 O(n)
易错点
面试追问把动画讲成自己的话
追问暴力法和排序加二分的复杂度差在哪,什么时候值得排序?
追问为什么排序后只要检查第一个不小于 a 减 d 的数就够了?
追问Java 用 Arrays.binarySearch 要注意什么?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
找出数组排序后的目标下标
LeetCode 2089 · 简单 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题