解法一：Prime算法+堆

一个最小生成树问题。

  1. import java.util.*;
  3. class Solution {
  4.     public int minCostConnectPoints(int[][] points) {
  5.         final int N = points.length;
  6.         Point[] ps = new Point[N];
  7.         for (int i = 0; i < N; ++i) {
  8.             ps[i] = new Point(N);
  9.         }
  10.         for (int i = 0; i < N - 1; ++i) {
  11.             for (int j = i + 1; j < N; ++j) {
  12.                 int dis = distance(points[i], points[j]);
  13.                 ps[i].nextList.add(new int[] { j, dis });
  14.                 ps[j].nextList.add(new int[] { i, dis });
  15.             }
  16.         }
  17.         Comparator<int[]> comparator = new Comparator<int[]>() {
  18.             @Override
  19.             public int compare(int[] o1, int[] o2) {
  20.                 return o1[1] - o2[1];
  21.             }
  22.         };
  23.         Queue<int[]> queue = new PriorityQueue<>(comparator);
  24.         ps[0].isVisited = true;
  25.         queue.addAll(ps[0].nextList);
  26.         int index = 1;
  27.         int ans = 0;
  28.         while (!queue.isEmpty() && index < N) {
  29.             int[] min = queue.poll();
  30.             if (ps[min[0]].isVisited) {
  31.                 continue;
  32.             }
  33.             ps[min[0]].isVisited = true;
  34.             ans += min[1];
  35.             ++index;
  36.             for (int[] pair : ps[min[0]].nextList) {
  37.                 if (!ps[pair[0]].isVisited) {
  38.                     queue.add(pair);
  39.                 }
  40.             }
  41.         }
  42.         return ans;
  43.     }
  45.     private int distance(int[] p1, int[] p2) {
  46.         return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
  47.     }
  48. }
  50. class Point {
  51.     boolean isVisited;
  52.     List<int[]> nextList;
  54.     public Point(int n) {
  55.         this.isVisited = false;
  56.         this.nextList = new ArrayList<>(n);
  57.     }
  58. }