两个数组间的距离值 图解题解
这道题到底在问什么
- 输入
- arr1=[4,5,8], arr2=[10,9,1,8], d=2
- 输出
- 2
- 输入
- arr1=[1,4,2,3], arr2=[-4,-3,6,10,20,30], d=3
- 输出
- 2
- 输入
- arr1=[2,1,100,3], arr2=[-5,-2,10,-3,7], d=6
- 输出
- 1
先想最直接的笨办法
现在轮到 arr1 的第 0 个数,值是 3。去 arr2 这排里挨个看,有没有哪个数跟它的距离不超过 2。只要找到一个,3 就出局;一个都没有,它才达标。（动画第 5 步）
最优解：一步一步想明白
- 3记牢一句:arr1 的每个数,去 arr2 找有没有距离 ≤ 2 的近邻;找不到才达标。下面每帧都在套这句。
- 4arr1 是上面这排 [3,4,10,7],arr2 放在右边侧栏 [9,8,0,7]。要做的事:把 arr1 的每个数轮流拿出来,到 arr2 里查有没有距离不超过 2 的邻居。一个邻居都没有的才算达标,最后数出有几个。先从第一个数 3 开始。
- 5现在轮到 arr1 的第 0 个数,值是 3。去 arr2 这排里挨个看,有没有哪个数跟它的距离不超过 2。只要找到一个,3 就出局;一个都没有,它才达标。
- 6arr2 的第 0 个数是 9,算一下距离 |3 减 9| = 6。6 比 2 大,这个数离得够远,接着看下一个。
- 7arr2 的第 1 个数是 8,算一下距离 |3 减 8| = 5。5 比 2 大,这个数离得够远,接着看下一个。
- 8arr2 的第 2 个数是 0,算一下距离 |3 减 0| = 3。3 比 2 大,这个数离得够远,接着看下一个。
- 9arr2 的第 3 个数是 7,算一下距离 |3 减 7| = 4。4 比 2 大,这个数离得够远,接着看下一个。
- 10arr2 整排都看完了,没有任何一个数跟 3 的距离落在 2 以内,所以 3 达标,标绿,计入答案。已确认达标 1 个。
- 11现在轮到 arr1 的第 1 个数,值是 4。去 arr2 这排里挨个看,有没有哪个数跟它的距离不超过 2。只要找到一个,4 就出局;一个都没有,它才达标。
- 12arr2 的第 0 个数是 9,算一下距离 |4 减 9| = 5。5 比 2 大,这个数离得够远,接着看下一个。
- 13arr2 的第 1 个数是 8,算一下距离 |4 减 8| = 4。4 比 2 大,这个数离得够远,接着看下一个。
- 14arr2 的第 2 个数是 0,算一下距离 |4 减 0| = 4。4 比 2 大,这个数离得够远,接着看下一个。
- 15arr2 的第 3 个数是 7,算一下距离 |4 减 7| = 3。3 比 2 大,这个数离得够远,接着看下一个。
- 16arr2 整排都看完了,没有任何一个数跟 4 的距离落在 2 以内,所以 4 达标,标绿,计入答案。已确认达标 2 个。
- 17现在轮到 arr1 的第 2 个数,值是 10。去 arr2 这排里挨个看,有没有哪个数跟它的距离不超过 2。只要找到一个,10 就出局;一个都没有,它才达标。
- 18arr2 的第 0 个数是 9,算一下距离 |10 减 9| = 1。1 不超过 2,这就是一个近邻,出局信号亮了,10 注定达不了标。后面几个还是顺手扫完看清楚。
- 19arr2 的第 1 个数是 8,算一下距离 |10 减 8| = 2。2 不超过 2,这就是一个近邻,出局信号亮了,10 注定达不了标。后面几个还是顺手扫完看清楚。
- 20arr2 的第 2 个数是 0,算一下距离 |10 减 0| = 10。10 比 2 大,这个数离得够远,接着看下一个。
- 21arr2 的第 3 个数是 7,算一下距离 |10 减 7| = 3。3 比 2 大,这个数离得够远,接着看下一个。
- 22这排里出现过距离不超过 2 的数,说明 10 有近邻,不达标,标红,不计入。已确认达标 2 个。
- 23现在轮到 arr1 的第 3 个数,值是 7。去 arr2 这排里挨个看,有没有哪个数跟它的距离不超过 2。只要找到一个,7 就出局;一个都没有,它才达标。
- 24arr2 的第 0 个数是 9,算一下距离 |7 减 9| = 2。2 不超过 2,这就是一个近邻,出局信号亮了,7 注定达不了标。后面几个还是顺手扫完看清楚。
- 25arr2 的第 1 个数是 8,算一下距离 |7 减 8| = 1。1 不超过 2,这就是一个近邻,出局信号亮了,7 注定达不了标。后面几个还是顺手扫完看清楚。
- 26arr2 的第 2 个数是 0,算一下距离 |7 减 0| = 7。7 比 2 大,这个数离得够远,接着看下一个。
- 27arr2 的第 3 个数是 7,算一下距离 |7 减 7| = 0。0 不超过 2,这就是一个近邻,出局信号亮了,7 注定达不了标。后面几个还是顺手扫完看清楚。
- 28这排里出现过距离不超过 2 的数,说明 7 有近邻,不达标,标红,不计入。已确认达标 2 个。
- 29arr1 的四个数都查完了。3 和 4 在 arr2 里找不到距离 ≤ 2 的近邻,达标涂绿;10 和 7 都有挨得很近的邻居,出局涂红。所以距离值就是这两个达标的数,答案 2,跟开头说的对上了。
⚠️ 容易写错的地方
✗ 错：把条件记反:以为 arr2 里「存在」近邻才计数
✓ 对：是 arr2 里「不存在」任何近邻,a 才计入答案
题目数的是「找不到近邻」的 a。一旦在 arr2 里碰到一个距离 ≤ d 的数,这个 a 就出局、不能计;整排都没碰到才达标。方向反了会把答案数成它的补集
✗ 错：距离用严格小于 d 来卡
✓ 对：是 ≤ d,距离正好等于 d 也算挨得近、要出局
题目写的是 |a 减 b| ≤ d。比如 a=10、b=8、d=2,距离正好 2,这也是近邻,a 要出局。写成 < d 会把卡在 d 这条线上的近邻漏掉,误判 a 达标
✗ 错：Java 里直接拿 Arrays.binarySearch 的返回值当下标
✓ 对：先判负:i = i < 0 ? -i - 1 : i 还原成插入位置再用
binarySearch 没找到目标时返回的是负数,是「负的插入点减一」。不还原直接当下标会取到错位置甚至负下标越界。Python 的 bisect_left、C++ 的 lower_bound 没有这个坑,直接给插入位置
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
sort(arr2.begin(), arr2.end());
int ans = 0;
for (int x : arr1) {
auto it = lower_bound(arr2.begin(), arr2.end(), x - d);
if (it == arr2.end() || *it > x + d) {
++ans;
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
Arrays.sort(arr2);
int ans = 0;
for (int x : arr1) {
int i = Arrays.binarySearch(arr2, x - d);
i = i < 0 ? -i - 1 : i;
if (i == arr2.length || arr2[i] > x + d) {
++ans;
}
}
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)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 两个数组间的距离值 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
暴力法和排序加二分的复杂度差在哪,什么时候值得排序?+
暴力是双层循环,arr1 每个数都把 arr2 整排扫一遍,时间是 m 乘 n。排序加二分先花 O(n log n) 把 arr2 排好,之后每个 a 只用一次二分 O(log n) 跳到第一个不小于 a 减 d 的数,总体是 (m 加 n) 乘 log n。当两个数组都比较大时,排序加二分明显更快;数据规模小的时候暴力反而更省心、也好写不容易错。
为什么排序后只要检查第一个不小于 a 减 d 的数就够了?+
排序后,第一个不小于 a 减 d 的数,是所有大于等于 a 减 d 的数里最小的那个,也就是最有可能落进区间 [a 减 d, a 加 d] 的候选。如果连它都大于 a 加 d,那它后面更大的数离 a 更远,区间里肯定一个都没有;如果它不存在,说明 arr2 全比 a 减 d 还小,同样进不了区间。所以只看这一个候选就能下结论,不必再逐个比。
Java 用 Arrays.binarySearch 要注意什么?+
binarySearch 在数组里找到目标时返回它的下标,没找到时返回的是负数,具体是「负的插入点减一」。所以拿到返回值要先判断正负:负数就用 i 等于负 i 减 1 还原成真正的插入位置,再去判断是否越界、那个位置的数是否大于 a 加 d。Python 的 bisect_left 和 C++ 的 lower_bound 直接返回插入位置,没有这个负数转换的步骤,这是 Java 这版最容易写错的地方。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 两个数组间的距离值 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。