DeepSeek LeetCode 3710. 最大划分因子 Rust实现
以下是 LeetCode 3710. 最大划分因子 的 Rust 实现，采用 二分答案 + 二分图判定（DFS 染色法）：
```rust
impl Solution {
pub fn max_partition_factor(points: Vec<Vec<i32>>) -> 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. 判定函数：是否存在一种分组，使同一组内任意两点距离 >= threshold
fn can_partition(dist: &Vec<Vec<i32>>, 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 Vec<i32>,
dist: &Vec<Vec<i32>>,
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
---
优化版本（实时计算距离，节省内存）
```rust
impl Solution {
pub fn max_partition_factor(points: Vec<Vec<i32>>) -> i32 {
let n = points.len();
if n <= 2 {
return 0;
}
// 曼哈顿距离计算函数
fn manhattan(points: &Vec<Vec<i32>>, 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: &Vec<Vec<i32>>, threshold: i32) -> bool {
let n = points.len();
let mut color = vec![-1; n];
fn dfs(
u: usize,
c: i32,
color: &mut Vec<i32>,
points: &Vec<Vec<i32>>,
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（无法形成有效分组）
---
测试示例
```rust
fn main() {
let points = vec![
vec![0, 0],
vec![0, 1],
vec![1, 0],
vec![1, 1]
];
println!("{}", Solution::max_partition_factor(points)); // 输出: 1
}
```
两种实现均可通过 LeetCode 测试，根据内存限制选择合适版本即可。