给你一个points 数组,表示 2D 平面上的一些点,其中 points[i] = [xi, yi] 。
连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 :|xi - xj| + |yi - yj| ,其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时,才认为所有点都已连接。
刚开始写出来的超出时间限制了:
class Solution { public int minCostConnectPoints(int[][] points) { if(points.length==1){ return 0; } int [][]cost=new int[points.length][points.length]; for(int i=0;i<points.length;i++){ for(int j=i;j<points.length;j++){ if(i==j){ cost[i][j]=Integer.MAX_VALUE; }else{ cost[i][j]=Math.abs(points[i][0]-points[j][0])+Math.abs(points[i][1]-points[j][1]); cost[j][i]=cost[i][j]; } } } List<Integer> in=new ArrayList(); List<Integer> out=new ArrayList(); for(int i=0;i<points.length;i++){ out.add(i); } in.add(0); out.remove(0); int i=1; int sum=0; while(in.size()<points.length){ sum=sum+helper(in,out,cost); } return sum; } public int helper(List<Integer> in,List<Integer> out,int [][]cost){ int min=Integer.MAX_VALUE; int minFlag=-1; for(Integer i:in){ for(Integer j:out){ if(cost[i][j]<min){ min=cost[i][j]; minFlag=j; } } } in.add(minFlag); out.remove(out.indexOf(minFlag)); return min; } }
看到一个优化,每次添加节点之后,更新一个ds[]是从未加入节点到树的最小值,比如i,j都在里面,k在外面,j是新加入的
那么ds[k]=min{ds[k],cost[j][k]},而且加入的要用Set存储,用list也会超出时间限制
class Solution { public int minCostConnectPoints(int[][] points) { if(points.length==1){ return 0; } int [][]cost=new int[points.length][points.length]; for(int i=0;i<points.length;i++){ for(int j=i+1;j<points.length;j++){ if(i==j){ cost[i][j]=Integer.MAX_VALUE; }else{ cost[i][j]=Math.abs(points[i][0]-points[j][0])+Math.abs(points[i][1]-points[j][1]); cost[j][i]=cost[i][j]; } } } Set<Integer> in=new HashSet(); int []ds=new int[points.length]; for(int i=0;i<points.length;i++){ ds[i]=cost[0][i]; } in.add(0); int sum=0; for(int i=1;i<points.length;i++){ int min=Integer.MAX_VALUE; int minF=-1; for(int j=0;j<points.length;j++){ if(!in.contains(j)&&ds[j]<min){ min=ds[j]; minF=j; } } in.add(minF); sum=sum+min; for(int j=0;j<points.length;j++){ if(cost[minF][j]<ds[j]){ ds[j]=cost[minF][j]; } } } return sum; } }