Question

1584. Min Cost to Connect All Points

中文文档

Description

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return _the minimum cost to make all points connected._ All points are connected if there is exactly one simple path between any two points.

 

Example 1:

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation: 

We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.

Example 2:

Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18

 

Constraints:

• 1 <= points.length <= 1000
• -106 <= xi, yi <= 106
• All pairs (xi, yi) are distinct.

Solutions

Solution 1

class Solution:
  def minCostConnectPoints(self, points: List[List[int]]) -> int:
    n = len(points)
    g = [[0] * n for _ in range(n)]
    dist = [inf] * n
    vis = [False] * n
    for i, (x1, y1) in enumerate(points):
      for j in range(i + 1, n):
        x2, y2 = points[j]
        t = abs(x1 - x2) + abs(y1 - y2)
        g[i][j] = g[j][i] = t
    dist[0] = 0
    ans = 0
    for _ in range(n):
      i = -1
      for j in range(n):
        if not vis[j] and (i == -1 or dist[j] < dist[i]):
          i = j
      vis[i] = True
      ans += dist[i]
      for j in range(n):
        if not vis[j]:
          dist[j] = min(dist[j], g[i][j])
    return ans

class Solution {
  public int minCostConnectPoints(int[][] points) {
    final int inf = 1 << 30;
    int n = points.length;
    int[][] g = new int[n][n];
    for (int i = 0; i < n; ++i) {
      int x1 = points[i][0], y1 = points[i][1];
      for (int j = i + 1; j < n; ++j) {
        int x2 = points[j][0], y2 = points[j][1];
        int t = Math.abs(x1 - x2) + Math.abs(y1 - y2);
        g[i][j] = t;
        g[j][i] = t;
      }
    }
    int[] dist = new int[n];
    boolean[] vis = new boolean[n];
    Arrays.fill(dist, inf);
    dist[0] = 0;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int j = -1;
      for (int k = 0; k < n; ++k) {
        if (!vis[k] && (j == -1 || dist[k] < dist[j])) {
          j = k;
        }
      }
      vis[j] = true;
      ans += dist[j];
      for (int k = 0; k < n; ++k) {
        if (!vis[k]) {
          dist[k] = Math.min(dist[k], g[j][k]);
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int minCostConnectPoints(vector<vector<int>>& points) {
    int n = points.size();
    int g[n][n];
    for (int i = 0; i < n; ++i) {
      int x1 = points[i][0], y1 = points[i][1];
      for (int j = i + 1; j < n; ++j) {
        int x2 = points[j][0], y2 = points[j][1];
        int t = abs(x1 - x2) + abs(y1 - y2);
        g[i][j] = t;
        g[j][i] = t;
      }
    }
    int dist[n];
    bool vis[n];
    memset(dist, 0x3f, sizeof(dist));
    memset(vis, false, sizeof(vis));
    dist[0] = 0;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int j = -1;
      for (int k = 0; k < n; ++k) {
        if (!vis[k] && (j == -1 || dist[k] < dist[j])) {
          j = k;
        }
      }
      vis[j] = true;
      ans += dist[j];
      for (int k = 0; k < n; ++k) {
        if (!vis[k]) {
          dist[k] = min(dist[k], g[j][k]);
        }
      }
    }
    return ans;
  }
};

func minCostConnectPoints(points [][]int) (ans int) {
  n := len(points)
  g := make([][]int, n)
  vis := make([]bool, n)
  dist := make([]int, n)
  for i := range g {
    g[i] = make([]int, n)
    dist[i] = 1 << 30
  }
  for i := range g {
    x1, y1 := points[i][0], points[i][1]
    for j := i + 1; j < n; j++ {
      x2, y2 := points[j][0], points[j][1]
      t := abs(x1-x2) + abs(y1-y2)
      g[i][j] = t
      g[j][i] = t
    }
  }
  dist[0] = 0
  for i := 0; i < n; i++ {
    j := -1
    for k := 0; k < n; k++ {
      if !vis[k] && (j == -1 || dist[k] < dist[j]) {
        j = k
      }
    }
    vis[j] = true
    ans += dist[j]
    for k := 0; k < n; k++ {
      if !vis[k] {
        dist[k] = min(dist[k], g[j][k])
      }
    }
  }
  return
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}

function minCostConnectPoints(points: number[][]): number {
  const n = points.length;
  const g: number[][] = Array(n)
    .fill(0)
    .map(() => Array(n).fill(0));
  const dist: number[] = Array(n).fill(1 << 30);
  const vis: boolean[] = Array(n).fill(false);
  for (let i = 0; i < n; ++i) {
    const [x1, y1] = points[i];
    for (let j = i + 1; j < n; ++j) {
      const [x2, y2] = points[j];
      const t = Math.abs(x1 - x2) + Math.abs(y1 - y2);
      g[i][j] = t;
      g[j][i] = t;
    }
  }
  let ans = 0;
  dist[0] = 0;
  for (let i = 0; i < n; ++i) {
    let j = -1;
    for (let k = 0; k < n; ++k) {
      if (!vis[k] && (j === -1 || dist[k] < dist[j])) {
        j = k;
      }
    }
    vis[j] = true;
    ans += dist[j];
    for (let k = 0; k < n; ++k) {
      if (!vis[k]) {
        dist[k] = Math.min(dist[k], g[j][k]);
      }
    }
  }
  return ans;
}

Solution 2

class Solution:
  def minCostConnectPoints(self, points: List[List[int]]) -> int:
    def find(x: int) -> int:
      if p[x] != x:
        p[x] = find(p[x])
      return p[x]

    n = len(points)
    g = []
    for i, (x1, y1) in enumerate(points):
      for j in range(i + 1, n):
        x2, y2 = points[j]
        t = abs(x1 - x2) + abs(y1 - y2)
        g.append((t, i, j))
    p = list(range(n))
    ans = 0
    for cost, i, j in sorted(g):
      pa, pb = find(i), find(j)
      if pa == pb:
        continue
      p[pa] = pb
      ans += cost
      n -= 1
      if n == 1:
        break
    return ans

class Solution {
  private int[] p;

  public int minCostConnectPoints(int[][] points) {
    int n = points.length;
    List<int[]> g = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
      int x1 = points[i][0], y1 = points[i][1];
      for (int j = i + 1; j < n; ++j) {
        int x2 = points[j][0], y2 = points[j][1];
        g.add(new int[] {Math.abs(x1 - x2) + Math.abs(y1 - y2), i, j});
      }
    }
    g.sort(Comparator.comparingInt(a -> a[0]));
    p = new int[n];
    for (int i = 0; i < n; ++i) {
      p[i] = i;
    }
    int ans = 0;
    for (int[] e : g) {
      int cost = e[0], i = e[1], j = e[2];
      if (find(i) == find(j)) {
        continue;
      }
      p[find(i)] = find(j);
      ans += cost;
      if (--n == 1) {
        return ans;
      }
    }
    return 0;
  }

  private int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

class Solution {
public:
  vector<int> p;

  int minCostConnectPoints(vector<vector<int>>& points) {
    int n = points.size();
    vector<vector<int>> g;
    for (int i = 0; i < n; ++i) {
      int x1 = points[i][0], y1 = points[i][1];
      for (int j = i + 1; j < n; ++j) {
        int x2 = points[j][0], y2 = points[j][1];
        g.push_back({abs(x1 - x2) + abs(y1 - y2), i, j});
      }
    }
    sort(g.begin(), g.end());
    p.resize(n);
    for (int i = 0; i < n; ++i) p[i] = i;
    int ans = 0;
    for (auto& e : g) {
      int cost = e[0], i = e[1], j = e[2];
      if (find(i) == find(j)) continue;
      p[find(i)] = find(j);
      ans += cost;
      if (--n == 1) return ans;
    }
    return 0;
  }

  int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
  }
};

func minCostConnectPoints(points [][]int) int {
  n := len(points)
  var g [][]int
  for i, p := range points {
    x1, y1 := p[0], p[1]
    for j := i + 1; j < n; j++ {
      x2, y2 := points[j][0], points[j][1]
      g = append(g, []int{abs(x1-x2) + abs(y1-y2), i, j})
    }
  }
  sort.Slice(g, func(i, j int) bool {
    return g[i][0] < g[j][0]
  })
  ans := 0
  p := make([]int, n)
  for i := range p {
    p[i] = i
  }
  var find func(x int) int
  find = func(x int) int {
    if p[x] != x {
      p[x] = find(p[x])
    }
    return p[x]
  }
  for _, e := range g {
    cost, i, j := e[0], e[1], e[2]
    if find(i) == find(j) {
      continue
    }
    p[find(i)] = find(j)
    ans += cost
    n--
    if n == 1 {
      return ans
    }
  }
  return 0
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}