题目

给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。

连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。

示例 1：输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]] 输出：20

解释：我们可以按照上图所示连接所有点得到最小总费用，总费用为 20 。

注意到任意两个点之间只有唯一一条路径互相到达。

示例 2：输入：points = [[3,12],[-2,5],[-4,1]] 输出：18

示例 3：输入：points = [[0,0],[1,1],[1,0],[-1,1]] 输出：4

示例 4：输入：points = [[-1000000,-1000000],[1000000,1000000]] 输出：4000000

示例 5：输入：points = [[0,0]] 输出：0

提示：1 <= points.length <= 1000

-106 <= xi, yi <= 106

所有点 (xi, yi) 两两不同。

解题思路分析

1、Kruskal-排序+并查集；时间复杂度O(n^2log(n))，空间复杂度O(n^2)

func minCostConnectPoints(points [][]int) int {
   n := len(points)
   arr := make([][3]int, 0)
   for i := 0; i < n; i++ {
      for j := i + 1; j < n; j++ {
         arr = append(arr, [3]int{i, j, dis(points[i], points[j])}) // a=>b c
      }
   }
   sort.Slice(arr, func(i, j int) bool {
      return arr[i][2] < arr[j][2]
   })
   return Kruskal(n, arr)
}

func Kruskal(n int, arr [][3]int) int {
   res := 0
   fa = Init(n)
   count := 0
   for i := 0; i < len(arr); i++ {
      a, b, c := arr[i][0], arr[i][1], arr[i][2]
      if query(a, b) == false {
         union(a, b)
         res = res + c
         count++
         if count == n-1 {
            break
         }
      }
   }
   return res
}

var fa []int

// 初始化
func Init(n int) []int {
   arr := make([]int, n)
   for i := 0; i < n; i++ {
      arr[i] = i
   }
   return arr
}

// 查询
func find(x int) int {
   if fa[x] != x {
      fa[x] = find(fa[x])
   }
   return fa[x]
}

// 合并
func union(i, j int) {
   fa[find(i)] = find(j)
}

func query(i, j int) bool {
   return find(i) == find(j)
}

func dis(a, b []int) int {
   return abs(a[0]-b[0]) + abs(a[1]-b[1])
}

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

2、Prime；时间复杂度O(n^2)，空间复杂度O(n^2)

func minCostConnectPoints(points [][]int) int {
   n := len(points)
   arr := make([][]int, n) // 邻接矩阵
   for i := 0; i < n; i++ {
      arr[i] = make([]int, n)
   }
   for i := 0; i < n; i++ {
      for j := i + 1; j < n; j++ {
         c := dis(points[i], points[j])
         arr[i][j] = c
         arr[j][i] = c
      }
   }
   return Prime(arr)
}

// Prime：传入邻接矩阵
func Prime(arr [][]int) int {
   res := 0
   n := len(arr)
   visited := make([]bool, n)
   target := 0
   visited[target] = true // 任选1个即可
   dis := make([]int, n)  // 任意选择的节点：到其它点的距离
   for i := 0; i < n; i++ {
      dis[i] = arr[target][i]
   }
   for i := 1; i < n; i++ { // 执行n-1次：n-1条边
      var index int
      minValue := math.MaxInt32
      for j := 0; j < n; j++ { // 寻找：未访问过的最短边
         if visited[j] == false && dis[j] < minValue {
            minValue = dis[j]
            index = j
         }
      }
      visited[index] = true    // 标记为访问过的点
      res = res + minValue     // 加上最短边
      for j := 0; j < n; j++ { // 更新距离：以index为起点，更新生成树到每一个非树顶点的距离
         if visited[j] == false && dis[j] > arr[index][j] {
            dis[j] = arr[index][j]
         }
      }
   }
   return res
}

func dis(a, b []int) int {
   return abs(a[0]-b[0]) + abs(a[1]-b[1])
}

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

3、Prime+堆优化；时间复杂度O(nlog(n))，空间复杂度O(n^2)

func minCostConnectPoints(points [][]int) int {
   n := len(points)
   arr := make([][]int, n) // 邻接矩阵
   for i := 0; i < n; i++ {
      arr[i] = make([]int, n)
   }
   for i := 0; i < n; i++ {
      for j := i + 1; j < n; j++ {
         c := dis(points[i], points[j])
         arr[i][j] = c
         arr[j][i] = c
      }
   }
   return Prime(arr)
}

// Prime-堆优化-邻接表
func Prime(arr [][]int) int {
   res := 0
   n := len(arr)
   visited := make([]bool, n)
   target := 0
   dis := make([]int, n) // 任意选择的节点：到其它点的距离
   for i := 0; i < n; i++ {
      dis[i] = math.MaxInt32
   }
   intHeap := make(IntHeap, 0)
   heap.Init(&intHeap)
   heap.Push(&intHeap, [2]int{0, target}) // [2]int{距离，下标}
   for intHeap.Len() > 0 {
      node := heap.Pop(&intHeap).([2]int)
      minValue, index := node[0], node[1]
      if visited[index] == true {
         continue
      }
      visited[index] = true
      res = res + minValue
      for j := 0; j < len(arr[index]); j++ {
         if visited[j] == false && dis[j] > arr[index][j] {
            dis[j] = arr[index][j]
            heap.Push(&intHeap, [2]int{arr[index][j], j})
         }
      }
   }
   return res
}

type IntHeap [][2]int

func (h IntHeap) Len() int {
   return len(h)
}

// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
   return h[i][0] < h[j][0]
}

func (h IntHeap) Swap(i, j int) {
   h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
   *h = append(*h, x.([2]int))
}

func (h *IntHeap) Pop() interface{} {
   value := (*h)[len(*h)-1]
   *h = (*h)[:len(*h)-1]
   return value
}

func dis(a, b []int) int {
   return abs(a[0]-b[0]) + abs(a[1]-b[1])
}

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

总结

Medium题目，最小生成树问题