Leetcode 1584 使用Kruskal&并查集算法如何优化提升运行速度？

你当前采用的是Kruskal最小生成树算法，性能核心瓶颈在于边的生成和排序开销：n个点的场景下你生成了n²条边，包含大量无效冗余边，排序百万级以上的边会占用绝大多数运行时间。

优化方案 #

1. 移除无效冗余边（低成本优化） #

你当前的双层循环i从0到n-1、j从0到n-1会生成两类无效内容：

• i == j的自环边，距离为0，完全不需要加入边列表
• 同一条无向边会被重复存储两次：(i,j,dist)和(j,i,dist)
  只需要把内层循环改为j从i+1到n-1，就能直接把边数减少一半以上，不需要改动其他逻辑即可获得明显提速。

2. 曼哈顿距离MST专用剪枝（核心优化） #

曼哈顿距离场景下有经典结论：构建MST时，每个点不需要和所有其他点连边，仅需要和4种坐标投影排序后的相邻点连边即可覆盖所有MST可能用到的边。具体是对下面4种变换后的坐标分别排序，仅连接排序后相邻的点：

• 变换1：(x + y, x)
• 变换2：(x - y, x)
• 变换3：(-x + y, x)
• 变换4：(-x - y, x)
  经过这个处理后总边数会从O(n²)降到O(n)，排序开销会大幅降低，是最核心的性能优化手段。

3. 并查集增加按秩合并优化 #

你当前的并查集只实现了路径压缩，Union操作是直接把一棵树挂载到另一棵树上，最坏情况会导致树深度过高。增加按秩（按树的大小或深度）合并后，可以保证并查集的操作时间复杂度几乎为常数，进一步提升遍历边时的处理速度。

4. 改用Prim算法适配稠密图场景 #

对于本题n≤1000的限制，Prim算法的O(n²)朴素实现性能会远优于Kruskal：不需要提前生成所有边、不需要排序，只需要维护每个点到当前生成树的最小距离即可，代码实现也更简洁。

import java.util.Arrays;

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        int totalCost = 0;
        // 存储每个点到当前生成树的最小曼哈顿距离
        int[] minDist = new int[n];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[0] = 0;
        // 标记点是否已经加入生成树
        boolean[] inMST = new boolean[n];

        for (int i = 0; i < n; i++) {
            // 找到距离生成树最近的未加入节点
            int curNode = -1;
            int curMin = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                if (!inMST[j] && minDist[j] < curMin) {
                    curMin = minDist[j];
                    curNode = j;
                }
            }
            // 把节点加入生成树，累加费用
            inMST[curNode] = true;
            totalCost += curMin;
            // 更新剩余节点到生成树的最小距离
            for (int j = 0; j < n; j++) {
                if (!inMST[j]) {
                    int dist = Math.abs(points[curNode][0] - points[j][0]) + Math.abs(points[curNode][1] - points[j][1]);
                    if (dist < minDist[j]) {
                        minDist[j] = dist;
                    }
                }
            }
        }
        return totalCost;
    }
}

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