2025-10-20：针对图的路径存在性查询Ⅱ。用go语言，有 n 个顶点，

今日快讯 2025年10月21日 04:37 0 admin

2025-10-20：针对图的路径存在性查询Ⅱ。用go语言，有 n 个顶点，编号从 0 到 n-1。给出一个长度为 n 的整数数组 nums 和一个整数 maxDiff。

构造一张无向无权图：当任意两个下标 i、j 满足 nums[i] 与 nums[j] 的差的绝对值不超过 maxDiff 时，在顶点 i 与顶点 j 之间连一条边。

再给出若干查询 queries，每个查询是一个长度为 2 的数组 [u, v]，要求返回从顶点 u 到顶点 v 的最短路径长度（以边数计）。

如果 u 与 v 之间不存在连通路径，则该查询的答案为 -1。

最终输出一个答案数组 answer，answer[i] 即对应 queries[i] 的最短距离结果。

1 <= n == nums.length <= 100000。

0 <= nums[i] <= 100000。

0 <= maxDiff <= 100000。

1 <= queries.length <= 100000。

queries[i] == [ui, vi]。

0 <= ui, vi < n。

输入: n = 3, nums = [3,6,1], maxDiff = 1, queries = [[0,0],[0,1],[1,2]]。

输出: [0,-1,-1]。

解释:

由于以下原因，任意两个节点之间都不存在边：

节点 0 和节点 1：|nums[0] - nums[1]| = |3 - 6| = 3 > 1

节点 0 和节点 2：|nums[0] - nums[2]| = |3 - 1| = 2 > 1

节点 1 和节点 2：|nums[1] - nums[2]| = |6 - 1| = 5 > 1

因此，不存在任何可以到达其他节点的节点，输出为 [0, -1, -1]。

题目来自力扣3534。

1. 问题理解与建模

我们有 n 个顶点，每个顶点 i 有一个数值 nums[i]。
如果两个顶点 i 和 j 满足 |nums[i] - nums[j]| <= maxDiff，则它们之间有一条无向边。
查询 [u, v] 要求它们之间的最短路径（边数），不连通则返回 -1。

2. 核心思路

直接建图会超时（n 可达 10^5，完全图边数太多），因此利用按数值排序 + 二进制提升的方法：

• 如果按 nums 值排序，那么满足 |nums[i] - nums[j]| <= maxDiff 的点在排序后的数组里是连续的一段。

• 对于排序后的数组，我们可以定义“可达范围”：从某个位置 i 出发，在满足数值差不超过 maxDiff 的条件下，最远能连续到达的位置。

• 这样问题转化为在排序后的索引序列上做“跳步”查询。

3. 算法步骤详解

3.1 排序并记录原索引

将 (nums[i], i) 按 nums 升序排序，得到数组 numsIndices。
同时建立 order 数组，order[原索引] = 排序后的位置，用于查询时快速定位。

例如：
nums = [3, 6, 1]
排序后：[(1, 2), (3, 0), (6, 1)]
那么 order[0] = 1（原顶点 0 在排序后位置 1），order[1] = 2，order[2] = 0。

3.2 计算每个位置的一步可达右边界

用双指针法（滑动窗口）：

• left 从 0 到 n-1

• 对每个 left，right 尽量右移，直到 nums[right+1] - nums[left] > maxDiff 为止。

• 则 successors[left][0] = right，表示从 left 出发一步能到达的最远位置（在排序数组中）。

注意：这里的一步不是直接边，而是在排序数组中数值差不超过 maxDiff 的连续段的最右端。
因为排序后，如果 i 能到 j（数值差 ≤ maxDiff），那么 i 到 i+1, i+2, ..., j 都可以直接或间接到达，并且可以一次跳很多位置。

3.3 二进制提升（Binary Lifting）

定义 successors[i][j] 表示从位置 i 出发，跳 2^j 步（在排序数组的连续可达范围内）能到达的最右位置。

递推公式：

successors[i][j] = successors[successors[i][j-1]][j-1]

即从 i 跳 2^(j-1) 步到 x，再从 x 跳 2^(j-1) 步。

这样我们就能快速计算从某个起点到某个终点的最小跳数。

3.4 处理查询

对于查询 [u, v]：

1. 找到它们在排序数组中的位置 start = order[u]，end = order[v]。

2. 如果 start > end，交换它们（因为排序数组上我们只向右跳）。

3. 如果 start == end，说明是同一个点，距离为 0。

4. 否则，用二进制提升法：

• 从 start 开始，从高到低尝试 j，如果 successors[index][j] < end，就跳 2^j 步，并累加距离。

• 最后检查跳一步是否能到 end（successors[index][0] >= end），如果能，则总距离加 1 即为答案；否则返回 -1（不可达）。

注意：这里“可达”是指排序数组上从 start 能经过若干次扩展最远边界跳到 end，对应原图中存在路径。
因为原图中如果数值差 ≤ maxDiff 则连边，排序后相邻点若满足差值条件则连通，所以排序数组上的连续段在原图中是连通的，并且跨段可以通过中间节点连通。

4. 复杂度分析

时间复杂度

• 排序：O(n log n)

• 双指针计算初始后继：O(n)

• 二进制提升表构建：O(n log n)

• 每个查询：O(log n)

• 总复杂度：O(n log n + q log n)，其中 q 是查询数量。

空间复杂度

• 排序数组：O(n)

• order 数组：O(n)

• successors 表：O(n log n)

• 总空间：O(n log n)

Go完整代码如下：

package mainimport (    "fmt"    "sort")func pathExistenceQueries(n int, nums []int, maxDiff int, queries [][]int) []int {    // 创建带索引的数组并排序    numsIndices := make([][2]int, n)    for i, num := range nums {        numsIndices[i] = [2]int{num, i}    }    sort.Slice(numsIndices, func(i, j int)bool {        return numsIndices[i][0] < numsIndices[j][0]    })    // 创建顺序映射    order := make([]int, n)    for i, item := range numsIndices {        order[item[1]] = i    }    // 计算二进制提升的长度    m := getLength(n)    // 创建后继数组    successors := make([][]int, n)    for i := range successors {        successors[i] = make([]int, m)    }    // 初始化第一层后继    left, right := 0, 0    for left < n {        for right+1 < n && numsIndices[right+1][0]-numsIndices[left][0] <= maxDiff {            right++        }        successors[left][0] = right        left++    }    // 构建二进制提升表    for j := 1; j < m; j++ {        for i := 0; i < n; i++ {            prevSuccessor := successors[i][j-1]            successors[i][j] = successors[prevSuccessor][j-1]        }    }    // 处理查询    q := len(queries)    answer := make([]int, q)    for i := 0; i < q; i++ {        start := order[queries[i][0]]        end := order[queries[i][1]]        if start > end {            start, end = end, start        }        if start == end {            answer[i] = 0        } else {            distance := 1            index := start            // 二进制提升查找            for j := m - 1; j >= 0; j-- {                if successors[index][j] < end {                    distance += 1 << j                    index = successors[index][j]                }            }            if successors[index][0] >= end {                answer[i] = distance            } else {                answer[i] = -1            }        }    }    return answer}func getLength(n int)int {    length := 0    for n > 0 {        n /= 2        length++    }    return length}func main() {    n := 3    nums := []int{3, 6, 1}    maxDiff := 1    queries := [][]int{{0, 0}, {0, 1}, {1, 2}}    result := pathExistenceQueries(n, nums, maxDiff, queries)    fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-def pathExistenceQueries(n, nums, maxDiff, queries):    # 创建带索引的数组并排序    nums_indices = [(num, i) for i, num in enumerate(nums)]    nums_indices.sort(key=lambda x: x[0])        # 创建顺序映射    order = [0] * n    for i, (_, original_idx) in enumerate(nums_indices):        order[original_idx] = i        # 计算二进制提升的长度    m = get_length(n)        # 创建后继数组    successors = [[0] * m for _ in range(n)]        # 初始化第一层后继    left, right = 0, 0    while left < n:        while right + 1 < n and nums_indices[right + 1][0] - nums_indices[left][0] <= maxDiff:            right += 1        successors[left][0] = right        left += 1        # 构建二进制提升表    for j in range(1, m):        for i in range(n):            prev_successor = successors[i][j - 1]            successors[i][j] = successors[prev_successor][j - 1]        # 处理查询    q = len(queries)    answer = [0] * q        for i in range(q):        start = order[queries[i][0]]        end = order[queries[i][1]]                if start > end:            start, end = end, start                if start == end:            answer[i] = 0        else:            distance = 1            idx = start                        # 二进制提升查找            for j in range(m - 1, -1, -1):                if successors[idx][j] < end:                    distance += 1 << j                    idx = successors[idx][j]                        if successors[idx][0] >= end:                answer[i] = distance            else:                answer[i] = -1        return answerdef get_length(n):    length = 0    while n > 0:        n //= 2        length += 1    return lengthif __name__ == "__main__":    n = 3    nums = [3, 6, 1]    maxDiff = 1    queries = [[0, 0], [0, 1], [1, 2]]    result = pathExistenceQueries(n, nums, maxDiff, queries)    print(result)