如何优化LeetCode 3629的BFS解决质数传送最小跳跃问题？

当前问题 #

我在解决LeetCode 3629题时，当前的BFS方案出现了TLE（超时），需要针对性优化。

当前实现思路与问题点 #

我采用BFS寻找最短路径，核心逻辑如下：

1. 每次从队列取出位置后，处理左右相邻的移动
2. 若当前位置的数值是质数，遍历整个数组，将所有能被该质数整除的未访问位置加入队列

简化代码如下：

queue<int> q;
vector<int> vis(n, 0);

q.push(0);
vis[0] = 1;

while (!q.empty()) {
    int i = q.front();
    q.pop();

    // 相邻位置移动
    if (i + 1 < n && !vis[i + 1]) {
        vis[i + 1] = 1;
        q.push(i + 1);
    }

    if (i - 1 >= 0 && !vis[i - 1]) {
        vis[i - 1] = 1;
        q.push(i - 1);
    }

    // 质数 teleport 逻辑
    if (isPrime(nums[i])) {
        for (int j = 0; j < n; j++) {
            if (j != i && nums[j] % nums[i] == 0 && !vis[j]) {
                vis[j] = 1;
                q.push(j);
            }
        }
    }
}

这个方案的核心瓶颈在于：每次遇到质数时都要遍历整个数组，如果数组规模大且质数多，时间复杂度会飙升到O(n²)，直接导致超时。

优化方案解答 #

1. BFS核心优化 #

核心是避免重复处理相同质数的teleport逻辑。当前代码中，只要遇到某个质数p，就会遍历整个数组找能被p整除的元素。但实际上，当我们第一次处理p时，所有能被p整除的元素都已经被加入队列或标记为访问，后续再遇到p时，不需要再重复遍历数组——因为这些元素要么已经被访问，要么已经在队列中等待处理。

可以维护一个已处理质数的集合：当处理某个质数p时，先检查是否已经处理过p，如果是则跳过teleport步骤；如果没有，则处理所有能被p整除的元素，然后将p加入已处理集合。

2. 预处理技术：筛法、质因数分解与哈希表分组 #

完全可以通过预处理避免每次遍历数组，具体步骤如下：

• 筛法预处理质数：用埃氏筛预处理出数组最大值以内的所有质数，将判断质数的时间复杂度从O(√x)降到O(1)。
• 哈希表按质因数分组：提前遍历数组，对每个元素分解出所有不同的质因数，将元素索引加入对应质因数的列表中。比如元素6的质因数是2、3，就把它的索引同时加入哈希表中2和3对应的列表。这样处理质数p时，直接从哈希表取出所有关联的元素索引，无需遍历整个数组。
• 质因数分解优化：只保留每个元素的不同质因数即可，因为只要元素能被p整除，不管p出现多少次，都只需要归组一次。

举个例子：数组元素是[6,10,15]，预处理后的哈希表为：

2: [0,1]
3: [0,2]
5: [1,2]

当处理位置0的元素6时，只需处理质因数2和3对应的列表，把未访问的索引加入队列，同时标记这两个质数为已处理，避免后续重复操作。

3. 最优时间复杂度分析 #

优化后的时间复杂度为O(n + m + s)：

• n是数组长度
• m是所有元素的质因数分解总次数（每个数的质因数数量远小于其本身，比如x≤1e6时质因数数量最多不超过7个）
• s是筛法预处理时间，取决于数组最大值MAX，筛法时间为O(MAX log log MAX)

该复杂度远低于原方案的O(n²)，能高效处理大规模数组。

内容的提问来源于stack exchange，提问作者Vishal V