LeetCode 1584. 连接所有点的最小费用

问题给定一个二维数组points其中points[i] [xi, yi]表示平面上的一个点。连接两个点[xi, yi]和[xj, yj]的费用为它们之间的曼哈顿距离|xi - xj| |yi - yj|要求把所有点都连接起来并且任意两个点之间都可以通过若干条边互相到达。返回连接所有点所需要的最小总费用。示例 1输入points [[0,0],[2,2],[3,10],[5,2],[7,0]]输出20解释用最小费用连接所有点总费用为20。示例 2输入points [[3,12],[-2,5],[-4,1]]输出18思路首先这道题的直觉解法很明显既然要让所有点都连通那我们可以在点和点之间连边。任意两个点之间都能连一条边边权就是它们的曼哈顿距离。那问题就变成了在一个完全图里选择一些边让所有点连通并且总费用最小。如果随便连边很容易多连出一些没必要的边。因为只要所有点能互相到达就够了不需要每两个点之间都直接连边。对于n个点来说真正需要的边数其实是n - 1条。那是不是可以把问题转化成“最小生成树”也就是在所有能连接全部节点的方案中找出边权总和最小的一棵树。怎么构造这棵最小生成树可以想到 Prim 算法。Prim 的想法是先从任意一个点开始把它当成当前已经连好的树。然后每次从还没加入树的点里选择一个“接入当前树代价最小”的点加入进来。不断重复直到所有点都加入树。拿变量来说minDist[i]表示点i接入当前这棵树的最小费用。一开始只有点0在树里所以minDist[0] 0 其他点 minDist INT_MAX每次选出未访问点中minDist最小的那个点u把它加入树并把这次接入费用加到答案里。那加入u后为什么要更新其他点的minDist因为u成了树的一部分其他还没加入树的点现在除了可以通过原来的树中节点接入也可以通过u接入。于是对每个未访问点x计算u到x的曼哈顿距离如果这个距离更小就更新minDist[x]。不难发现这个过程就是一直选择当前最便宜的连接方式把一个新点接入已经形成的树里。等所有点都加入后得到的总费用就是最小连接费用。解决先定义几个关键变量。minDist[i] 表示点 i 接入当前生成树的最小费用 visited[i] 表示点 i 是否已经加入生成树 res 表示当前总费用一开始选择点0作为起点所以设置minDist[0] 0循环n次每次向生成树中加入一个点。在所有还没访问过的点里找到minDist最小的点u!visited[j] minDist[j] 最小这个点就是当前接入生成树代价最小的点。把点u加入生成树。标记visited[u] true并把它的接入费用加入答案res minDist[u]更新其他未访问点的最小接入费用。对于每个还没加入生成树的点x计算它和u之间的曼哈顿距离abs(points[u][0] - points[x][0]) abs(points[u][1] - points[x][1])如果通过u接入更便宜就更新minDist[x]。注意这里不需要提前把所有边存下来。因为任意两个点之间的距离都可以直接通过坐标计算出来所以每次加入新点后现场计算并更新即可。classSolution{public:intminCostConnectPoints(vectorvectorintpoints){intnpoints.size();vectorintminDist(n,INT_MAX);vectorboolvisited(n,false);intres0;minDist[0]0;for(inti0;in;i){intu-1;for(intj0;jn;j){if(!visited[j](u-1||minDist[j]minDist[u])){uj;}}visited[u]true;resminDist[u];for(intx0;xn;x){if(!visited[x]){intdistabs(points[u][0]-points[x][0])abs(points[u][1]-points[x][1]);if(minDist[x]dist){minDist[x]dist;}}}}returnres;}};时间复杂度为O(n^2)因为每次选点需要遍历所有点更新距离也需要遍历所有点空间复杂度为O(n)主要用于minDist和visited数组。