同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个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)
两两不同。方法一:朴素 Prim 算法
我们定义一个数组 $dist$,其中 $dist[i]$ 表示点 $i$ 到当前生成树的距离,初始时 $dist[0] = 0$,其余均为 $+\infty$,定义一个数组 $vis$,其中 $vis[i]$ 表示点 $i$ 是否在生成树中,初始时所有点均不在生成树中,定义一个二维数组 $g$,其中 $g[i][j]$ 表示点 $i$ 到点 $j$ 的距离,那么我们的目标是将所有点都加入到生成树中,且总费用最小。
我们每次从不在生成树中的点中选取一个距离最小的点 $i$,将点 $i$ 加入到生成树中,并将 $i$ 到其它点的距离更新到 $dist$ 数组中,直到所有点都在生成树中为止。
该算法适用于稠密图,时间复杂度 $O(n^2)$,空间复杂度 $O(n^2)$。其中 $n$ 为点的数量。
方法二:Kruskal 算法
我们先将所有边按照长度由小到大进行排序,循环遍历每条边,逐个加入到图中,当所有点达到一个连通状态时,退出循环,返回此时的总费用即可。
时间复杂度 $O(m \times \log m)$,空间复杂度 $O(m)$。其中 $m$ 为边的数量,本题中 $m = n^2$。
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:
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 {
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 {
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:
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;
}
};
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) (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 min(a, b int) int {
if a < b {
return a
}
return b
}
func abs(x int) int {
if x < 0 {
return -x
}
return 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
}
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;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。