DeepSeek LeetCode 3710. 最大划分因子 Rust实现

以下是 LeetCode 3710. 最大划分因子 的 Rust 实现采用 二分答案 二分图判定DFS 染色法rustimpl Solution {pub fn max_partition_factor(points: VecVeci32) - i32 {let n points.len();if n 2 {return 0;}// 1. 计算所有点对之间的曼哈顿距离let mut dist vec![vec![0; n]; n];let mut max_dist 0;for i in 0..n {let (x1, y1) (points[i][0], points[i][1]);for j in (i 1)..n {let (x2, y2) (points[j][0], points[j][1]);let d (x1 - x2).abs() (y1 - y2).abs();dist[i][j] d;dist[j][i] d;max_dist max_dist.max(d);}}// 2. 判定函数是否存在一种分组使同一组内任意两点距离 thresholdfn can_partition(dist: VecVeci32, threshold: i32) - bool {let n dist.len();let mut color vec![-1; n]; // -1: 未染色, 0/1: 两组// DFS 染色fn dfs(u: usize,c: i32,color: mut Veci32,dist: VecVeci32,threshold: i32,) - bool {color[u] c;for v in 0..dist.len() {if u v {continue;}// 距离小于阈值则必须分到不同组if dist[u][v] threshold {if color[v] -1 {if !dfs(v, c ^ 1, color, dist, threshold) {return false;}} else if color[v] c {return false;}}}true}for i in 0..n {if color[i] -1 {if !dfs(i, 0, mut color, dist, threshold) {return false;}}}true}// 3. 二分查找最大可行阈值let mut left 0;let mut right max_dist;while left right {let mid (left right 1) / 2;if can_partition(dist, mid) {left mid;} else {right mid - 1;}}left}}---核心思路解析问题转化· 对于给定阈值 d判断能否将所有点分成两组使得同一组内任意两点的曼哈顿距离 ≥ d· 等价于距离 d 的点对必须分到不同组建图与判定· 如果两点距离 d在它们之间建立一条边· 问题转化为这个图是否是二分图能否用2种颜色染色· 使用 DFS 染色法检测是否存在奇环二分答案· 答案具有单调性d 越大越难满足· 二分搜索最大可行的 d---优化版本实时计算距离节省内存rustimpl Solution {pub fn max_partition_factor(points: VecVeci32) - i32 {let n points.len();if n 2 {return 0;}// 曼哈顿距离计算函数fn manhattan(points: VecVeci32, i: usize, j: usize) - i32 {(points[i][0] - points[j][0]).abs() (points[i][1] - points[j][1]).abs()}// 计算最大距离作为二分上界let mut max_dist 0;for i in 0..n {for j in (i 1)..n {let d manhattan(points, i, j);max_dist max_dist.max(d);}}// 判定函数fn can_partition(points: VecVeci32, threshold: i32) - bool {let n points.len();let mut color vec![-1; n];fn dfs(u: usize,c: i32,color: mut Veci32,points: VecVeci32,threshold: i32,) - bool {color[u] c;for v in 0..points.len() {if u v {continue;}let d (points[u][0] - points[v][0]).abs() (points[u][1] - points[v][1]).abs();if d threshold {if color[v] -1 {if !dfs(v, c ^ 1, color, points, threshold) {return false;}} else if color[v] c {return false;}}}true}for i in 0..n {if color[i] -1 {if !dfs(i, 0, mut color, points, threshold) {return false;}}}true}let mut left 0;let mut right max_dist;while left right {let mid (left right 1) / 2;if can_partition(points, mid) {left mid;} else {right mid - 1;}}left}}---复杂度分析· 时间复杂度O(N² log M)N 为点数M 为最大曼哈顿距离· 二分查找执行 O(log M) 次· 每次判定遍历所有点对 O(N²)· 空间复杂度· 预计算版本O(N²)· 实时计算版本O(N)---注意事项1. Rust 所有权与借用DFS 闭包需要正确传递 mut color 和不可变引用2. 整数类型坐标范围为 i32距离计算不会溢出3. 二分边界使用 (left right 1) / 2 避免死循环4. 特殊处理n 2 时返回 0无法形成有效分组---测试示例rustfn main() {let points vec![vec![0, 0],vec![0, 1],vec![1, 0],vec![1, 1]];println!({}, Solution::max_partition_factor(points)); // 输出: 1}两种实现均可通过 LeetCode 测试根据内存限制选择合适版本即可。