2024-11-23：最小化曼哈顿距离。用go语言，给定一个从0开始的数组 points，其中每个元素 points[i] =

2024-11-23：最小化曼哈顿距离。用go语言，给定一个从0开始的数组 points，其中每个元素 points[i] = [xi, yi] 表示二维平面上的一个点的整数坐标。我们使用曼哈顿距离来定义两点之间的距离。

你的任务是恰好移除一个点，返回在移除该点后，任意两点之间最大距离的最小可能值。

输入：points = [[3,10],[5,15],[10,2],[4,4]]。

输出：12。

解释：移除每个点后的最大距离如下所示：

1.移除第 0 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间，为 |5 - 10| + |15 - 2| = 18 。

2.移除第 1 个点后，最大距离在点 (3, 10) 和 (10, 2) 之间，为 |3 - 10| + |10 - 2| = 15 。

3.移除第 2 个点后，最大距离在点 (5, 15) 和 (4, 4) 之间，为 |5 - 4| + |15 - 4| = 12 。

4.移除第 3 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间的，为 |5 - 10| + |15 - 2| = 18 。

在恰好移除一个点后，任意两点之间的最大距离可能的最小值是 12 。

答案2024-11-23：

chatgpt

题目来自leetcode3102。

大体步骤如下：

1.初始化和输入处理：

• 接收二维数组points，其中每个元素points[i] = [xi, yi]表示二维平面上的一个点。

• 获取点的数量n。

2.创建坐标组合：

2.1.构造两个数组sx和sy，用于存储两个不同计算方式下的坐标：

2.1.1.sx[i] = [xi - yi, i]：表示通过计算每个点的x和y坐标差值。

2.1.2.sy[i] = [xi + yi, i]：表示通过计算每个点的x和y坐标和。

3.排序：

• 将sx按照第一个元素（即xi - yi）进行排序，以便后续计算曼哈顿距离时易于访问最大值和最小值。

• 将sy同样按第一个元素（即xi + yi）进行排序。

4.计算极值：

4.1.计算maxVal1和maxVal2：

4.1.1.maxVal1为sx最后一个元素和第一个元素的差值，表示在差值坐标系下的最大距离。

4.1.2.maxVal2为sy最后一个元素和第一个元素的差值，表示在和坐标系下的最大距离。

5.初始化最小结果：

• 初始化一个变量res为一个非常大的整数，这个变量将用于记录在去掉一个点后可能产生的最小最大距离。

6.选择去掉的点：

6.1.根据maxVal1和maxVal2的大小进行判断，找出更大的那种方式（差值或和）：

6.1.1.如果maxVal1≥maxVal2，则选择从sx中的最小值i和最大值j（即sx[0]和sx[n - 1]的索引）进行去除，计算这些情形下的最大距离。

6.1.2.否则，选择从sy中的最小值i和最大值j（即sy[0]和sy[n - 1]的索引）进行去除，计算这些情形下的最大距离。

7.计算最大距离：

7.1.对于每一个去除的点（索引i或j），使用remove函数计算去除后的最大曼哈顿距离：

7.1.1.remove函数根据去除的点的索引返回在该点无法参与计算状态下的最大距离。

8.更新最小结果：

• 对每次计算的最大曼哈顿距离与res进行比较，保留更小的值。

9.返回结果：

• 函数最终返回res，即在去掉一个点后，剩下点之间的最大距离的最小值。

时间和空间复杂度分析：

时间复杂度：

• 对于n个点，构造sx和sy需要 O(n) 的时间。

• 排序操作对于sx和sy都是 O(n log n)。

• 计算每个点去除后的最大距离，最坏情况需要 O(n)，因为我们最多遍历一次点的数组。

• 因此，总的时间复杂度为 O(n log n)。

空间复杂度：

• 我们使用了额外的数组sx和sy，每个大小为n，两者总共占用 O(n) 的空间。

• 其他只使用了常量级别的空间（如变量res、maxVal1和maxVal2）。

• 因此，总的额外空间复杂度为 O(n)。

Go完整代码如下：

package main

import(

"fmt"

"sort"

)

func minimumDistance(points [][]int)int{

n :=len(points)

sx :=make([][]int, n)

sy :=make([][]int, n)

for i :=0; i < n; i++{

x, y := points[i][0], points[i][1]

sx[i]=[]int{x - y, i}

sy[i]=[]int{x + y, i}

}

sort.Slice(sx,func(i, j int)bool{

return sx[i][0]< sx[j][0]

})

sort.Slice(sy,func(i, j int)bool{

return sy[i][0]< sy[j][0]

})

maxVal1 := sx[n -1][0]- sx[0][0]

maxVal2 := sy[n -1][0]- sy[0][0]

res :=int(^uint(0)>>1)

if maxVal1 >= maxVal2 {

i, j := sx[0][1], sx[n -1][1]

// 去掉 i 后的最大曼哈顿距离

res = min(res, max(remove(sx, i), remove(sy, i)))

// 去掉 j 后的最大曼哈顿距离

res = min(res, max(remove(sx, j), remove(sy, j)))

}else{

i, j := sy[0][1], sy[n -1][1]

// 去掉 i 后的最大曼哈顿距离

res = min(res, max(remove(sx, i), remove(sy, i)))

// 去掉 j 后的最大曼哈顿距离

res = min(res, max(remove(sx, j), remove(sy, j)))

}

return res

}

func remove(arr [][]int, i int)int{

n :=len(arr)

if arr[0][1]== i {

return arr[n -1][0]- arr[1][0]

}elseif arr[n -1][1]== i {

return arr[n -2][0]- arr[0][0]

}else{

return arr[n -1][0]- arr[0][0]

}

}

func main(){

points :=[][]int{{3,10},{5,15},{10,2},{4,4}}

fmt.Println(minimumDistance(points))

}

在这里插入图片描述Rust完整代码如下：

use std::cmp::{min, max};

use std::vec::Vec;

fnminimum_distance(points:Vec<Vec<i32>>)->i32{

letn= points.len();

letmut sx:Vec<(i32,usize)>=Vec::with_capacity(n);

letmut sy:Vec<(i32,usize)>=Vec::with_capacity(n);

foriin0..n {

letx= points[i][0];

lety= points[i][1];

sx.push((x - y, i));

sy.push((x + y, i));

}

sx.sort_by(|a, b| a.0.cmp(&b.0));

sy.sort_by(|a, b| a.0.cmp(&b.0));

letmax_val1= sx[n -1].0- sx[0].0;

letmax_val2= sy[n -1].0- sy[0].0;

letmut res= i32::MAX;

if max_val1 >= max_val2 {

let(i, j)=(sx[0].1, sx[n -1].1);

// 去掉 i 后的最大曼哈顿距离

res =min(res,max(remove(&sx, i),remove(&sy, i)));

// 去掉 j 后的最大曼哈顿距离

res =min(res,max(remove(&sx, j),remove(&sy, j)));

}else{

let(i, j)=(sy[0].1, sy[n -1].1);

// 去掉 i 后的最大曼哈顿距离

res =min(res,max(remove(&sx, i),remove(&sy, i)));

// 去掉 j 后的最大曼哈顿距离

res =min(res,max(remove(&sx, j),remove(&sy, j)));

}

res

}

fnremove(arr:&[(i32,usize)], i:usize)->i32{

letn= arr.len();

if arr[0].1== i {

return arr[n -1].0- arr[1].0;

}elseif arr[n -1].1== i {

return arr[n -2].0- arr[0].0;

}else{

return arr[n -1].0- arr[0].0;

}

}

fnmain(){

letpoints=vec![vec![3,10],vec![5,15],vec![10,2],vec![4,4]];

println!("{}",minimum_distance(points));

}

在这里插入图片描述