Kimi LeetCode 3534. 针对图的路径存在性查询 II Rust实现
以下是 LeetCode 3534. 针对图的路径存在性查询 II 的完整 Rust 实现。
---
核心思路
与 Java/Python 版本一致：
1. 排序：按 `nums` 值排序，记录原始下标到排序后位置的映射。
2. 双指针求最远跳：`nxt[i]` 表示从排序后位置 `i` 一步能到达的最远位置。
3. 倍增预处理：`jump[i][k]` 表示从 `i` 连续做 `2^k` 次"最远跳"到达的位置。
4. 查询贪心：同一连通分量内，从高位到低位尝试跳跃，求最少步数。
时间复杂度：`O(n log n + q log n)`，空间复杂度：`O(n log n)`。
---
Rust 代码
```rust
use std::collections::HashMap;
impl Solution {
pub fn path_existence_queries(n: i32, nums: Vec<i32>, max_diff: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
let n = n as usize;
let max_diff = max_diff as i64;
// 1. 按 nums 值排序，记录原始下标 -> 排序后位置的映射
let mut order: Vec<usize> = (0..n).collect();
order.sort_by_key(|&i| nums[i]);
let mut sorted_nums = vec![0i64; n];
let mut pos = vec![0usize; n];
for (i, &idx) in order.iter().enumerate() {
sorted_nums[i] = nums[idx] as i64;
pos[idx] = i;
}
// 2. 计算连通分量编号（排序后连续段）
let mut comp = vec![0usize; n];
for i in 1..n {
comp[i] = comp[i - 1];
if sorted_nums[i] - sorted_nums[i - 1] > max_diff {
comp[i] += 1;
}
}
// 3. 双指针求 nxt[i]：从排序后位置 i 一步能跳到的最远位置
let mut nxt = vec![0usize; n];
let mut r = 0usize;
for i in 0..n {
while r + 1 < n && sorted_nums[r + 1] - sorted_nums[i] <= max_diff {
r += 1;
}
nxt[i] = r;
}
// 4. 倍增数组：jump[i][k] 表示从 i 连续跳 2^k 次最远跳到达的位置
let log = (n + 1).next_power_of_two().trailing_zeros() as usize;
let mut jump = vec![vec![0usize; log]; n];
for i in 0..n {
jump[i][0] = nxt[i];
}
for k in 1..log {
for i in 0..n {
jump[i][k] = jump[jump[i][k - 1]][k - 1];
}
}
// 5. 回答查询
let mut ans = Vec::with_capacity(queries.len());
for q in &queries {
let u = q[0] as usize;
let v = q[1] as usize;
if u == v {
ans.push(0);
continue;
}
let mut pu = pos[u];
let mut pv = pos[v];
if pu > pv {
std::mem::swap(&mut pu, &mut pv);
}
// 不在同一连通分量，不可达
if comp[pu] != comp[pv] {
ans.push(-1);
continue;
}
// 倍增贪心：从高位到低位，能跳就跳，求最少步数
let mut cur = pu;
let mut steps = 0i32;
for k in (0..log).rev() {
if jump[cur][k] < pv {
steps += (1 << k) as i32;
cur = jump[cur][k];
}
}
// 最后一步一定能到达 pv
ans.push(steps + 1);
}
ans
}
}
```
---
关键点说明
步骤 说明
排序映射 `pos[u]` 将原始节点编号映射到排序后的位置。Rust 中需小心 `usize` 与 `i32` 的类型转换。
连通分量 排序后，若相邻元素差 `> max_diff`，则开启新连通分量。查询时先判断 `comp[pu] == comp[pv]`。
最远跳 `nxt` 双指针在 `O(n)` 内求出每个位置一步能覆盖的最远范围。`nxt[i]` 单调不降。
倍增 `jump` `jump[i][k]` 表示从 `i` 出发连续做 `2^k` 次贪心最远跳到达的位置。利用 `next_power_of_two().trailing_zeros()` 计算所需层数。
查询贪心 从 `pu` 到 `pv`，从高位到低位尝试：如果跳 `2^k` 步后仍到不了 `pv`，就先跳这 `2^k` 步。最终剩余距离只需一步即可覆盖。
> 注意：Rust 中 `nums` 值差可能溢出 `i32`，因此内部计算时转换为 `i64` 处理。