2026-01-03: 通过质数传送到达终点的最少跳跃次数。用go语言, 给

2026-01-03：通过质数传送到达终点的最少跳跃次数。用go语言，给定一个长度为 n 的整数数组 nums。你从数组左端的第一个位置出发，目标是抵达最后一个位置（索引为 n-1）。在任一位置 i 上，你可以选择两类动作：

• 移动到相邻位置：走到 i+1 或 i-1（前提是该索引在数组范围内）。

• 质数传送：如果当前位置的数 nums[i] 是质数 p，那么你可以立即跳到数组中任意一个下标 j（j ≠ i），只要 nums[j] 能被 p 整除（即 nums[j] % p == 0）。

要求计算从起点到终点所需的最少跳跃次数。

备注：质数指大于 1、且只有 1 和自身两个正因子的整数。

1

1

输入: nums = [1,2,4,6]。

输出: 2。

解释:

一个最优的跳跃序列是：

从下标 i = 0 开始。向相邻下标 1 跳一步。

在下标 i = 1，nums[1] = 2 是一个质数。因此，我们传送到索引 i = 3，因为 nums[3] = 6 可以被 2 整除。

因此，答案是 2。

题目来自力扣3629。

大体步骤如下：

预处理质因子

首先，代码通过埃拉托斯特尼筛法的变种，预先计算每个数（最多到1,000,000）的所有质因数，并存储在全局数组 primeFactors 中。这样，在后续需要获取任意一个数的质因数时，就可以实现O(1)时间复杂度的查询。

构建质数分组索引

接着，代码遍历输入的数组 nums，为每个质数建立一个索引列表。具体来说，如果一个数 x 是质数（即它的质因数列表长度为1），那么程序会记录下所有数值等于 x 的位置索引。这个结构 groups 的键是质数本身，值是该质数在数组中出现的所有位置列表。

使用BFS寻找最短路径

核心的搜索过程采用广度优先搜索（BFS），并且是从终点向起点反向搜索。BFS可以保证一旦搜索到起点，所经历的步数就是最短路径。

1. 初始化：队列 q 初始时只包含终点（索引 n-1），并标记为已访问。步数 ans 初始为0。

2. 层级遍历：在每一轮循环中，处理当前队列 tmp 中的所有节点（这些节点距离终点的步数相同）。然后为每个节点生成所有可能的下一跳节点，放入新的队列 q 中，同时步数 ans 加1。

3. 生成下一跳节点：对于当前处理的节点 i，考虑三种移动方式：

• 向左移动：跳到索引 i-1（如果存在且未被访问过）。

• 向右移动：跳到索引 i+1（如果存在且未被访问过）。

• 质数传送：这是最关键的一步。找出 nums[i] 的所有质因数 p。对于每个质因数 p，通过预建的 groups 映射，找到数组中所有数值能被 p 整除的位置 j，并将这些位置作为下一跳。为了避免重复处理和提升效率，每当一个质因数 p 被使用后，会将其从 groups 中删除。

4. 终止条件：如果在处理当前层级的节点时，发现了起点（索引 0），则立即返回当前的步数 ans 作为答案。

⏱️ 复杂度分析

复杂度类型

结果

分析依据

时间复杂度

O(N + M log log M)

N

是数组 nums 的长度，M 是数组中数值的最大可能值（1,000,000）。预处理质因数的埃氏筛法复杂度约为 O(M log log M)。BFS过程中，每个节点最多被访问一次，每条边（移动方式）最多被尝试一次。特别地，由于使用了删除操作，每个质因数对应的节点列表最多被整体访问一次，这保证了BFS的整体复杂度与节点和边的数量呈线性关系，主要部分为 O(N)。

空间复杂度

O(N + M)

主要用于存储 primeFactors 数组（O(M)）和 groups 映射、BFS队列、访问标记数组等（O(N)）。

核心思路总结

这个解法的巧妙之处在于：

• 反向BFS：从终点出发，只需一次搜索即可找到起点到终点的最短路径。

• 预处理与索引：通过预处理质因数列表和构建质数分组索引，将复杂的“质数传送”操作转化为高效的查询。

• 剪枝优化：在BFS中使用删除操作避免对同一质因数对应的节点列表进行重复检查，是控制复杂度的关键。

Go完整代码如下：

package main

import (

"fmt"

)

const mx = 1_000_001

var primeFactors = [mx][]int{}

func init {

// 预处理每个数的质因子列表，思路同埃氏筛

for i := 2; i

if primeFactors[i] == nil { // i 是质数

for j := i; j

primeFactors[j] = append(primeFactors[j], i)

}

}

}

}

func minJumps(nums []int) (ans int) {

n := len(nums)

groups := map[int][]int{}

for i, x := range nums {

iflen(primeFactors[x]) == 1 { // x 是质数

groups[x] = append(groups[x], i)

}

}

vis := make([]bool, n)

vis[n-1] = true

q := []int{n - 1}

for {

tmp := q

q = nil

for _, i := range tmp {

if i == 0 {

return

}

if !vis[i-1] {

vis[i-1] = true

q = append(q, i-1)

}

if i

vis[i+1] = true

q = append(q, i+1)

}

// 逆向思维：从 i 倒着跳到 nums[i] 的质因子 p 的下标 j

for _, p := range primeFactors[nums[i]] {

for _, j := range groups[p] {

if !vis[j] {

vis[j] = true

q = append(q, j)

}

}

delete(groups, p) // 避免重复访问下标列表

}

}

ans++

}

}

func main {

nums := []int{1, 2, 4, 6}

result := minJumps(nums)

fmt.Println(result)

}

Python完整代码如下：

# -*-coding:utf-8-*-

from collections import defaultdict, deque

mx = 1_000_001

prime_factors = [[] for _ in range(mx)]

def init:

"""预处理每个数的质因子列表，思路同埃氏筛"""

for i in range(2, mx):

if not prime_factors[i]: # i 是质数

for j in range(i, mx, i): # i 的倍数有质因子 i

prime_factors[j].append(i)

init

def min_jumps(nums: list[int]) -> int:

n = len(nums)

groups = defaultdict(list)

for i, x in enumerate(nums):

# 只处理质数（只有一个质因子且大于1）

if x > 1 and len(prime_factors[x]) == 1:

groups[x].append(i)

vis = [False] * n

vis[n - 1] = True

q = deque([n - 1])

ans = 0

while q:

for _ in range(len(q)):

i = q.popleft

if i == 0:

return ans

# 向左跳

if i - 1 >= 0 and not vis[i - 1]:

vis[i - 1] = True

q.append(i - 1)

# 向右跳

if i + 1

vis[i + 1] = True

q.append(i + 1)

# 跳转到相同质因子的位置

for p in prime_factors[nums[i]]:

if p in groups:

for j in groups[p]:

if not vis[j]:

vis[j] = True

q.append(j)

# 避免重复访问，删除该质因子的记录

del groups[p]

ans += 1

return-1 # 理论上题目保证可达，这里保留返回-1的健壮性

if __name__ == "__main__":

nums = [1, 2, 4, 6]

result = min_jumps(nums)

print(result)

C++完整代码如下：

#include

#include

#include

#include

#include

using namespace std;

constint MX = 1000001;

vector primeFactors[MX];

void init {

// 预处理每个数的质因子列表，思路同埃氏筛

for (int i = 2; i

if (primeFactors[i].empty) { // i 是质数

for (int j = i; j

primeFactors[j].push_back(i);

}

}

}

}

int minJumps(vector& nums) {

int n = nums.size;

unordered_map> groups;

for (int i = 0; i

int x = nums[i];

// x 是质数（只有一个质因子且大于1）

if (x > 1 && primeFactors[x].size == 1) {

groups[x].push_back(i);

}

}

vector vis(n, false);

vis[n - 1] = true;

queue q;

q.push(n - 1);

int ans = 0;

while (!q.empty) {

int size = q.size;

for (int k = 0; k

int i = q.front;

q.pop;

if (i == 0) return ans;

// 向左跳

if (i - 1 >= 0 && !vis[i - 1]) {

vis[i - 1] = true;

q.push(i - 1);

}

// 向右跳

if (i + 1

vis[i + 1] = true;

q.push(i + 1);

}

// 跳转到相同质因子的位置

for (int p : primeFactors[nums[i]]) {

auto it = groups.find(p);

if (it != groups.end) {

for (int j : it->second) {

if (!vis[j]) {

vis[j] = true;

q.push(j);

}

}

groups.erase(it); // 避免重复访问下标列表

}

}

}

ans++;

}

return-1; // 理论上题目保证可达，这里保留返回-1的健壮性

}

int main {

init;

vector nums = {1, 2, 4, 6};

int result = minJumps(nums);

cout

return0;

}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。

欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。